[C언어 뻘짓] 정렬 다 될때 까지 숨참는다!

정렬 다 될 까지 숨참는다!

 

라고 적혀있는데요?

 

---

 

BOGO SORT 

 

정렬이긴 한데 무작위 정렬이다. 정렬이 될 때까지 계속 정렬을 시도한다는 게 이 정렬에 특징이다.

무작위로 정렬을 해주기 때문에 운만 좋으면 빨리 될 수도 있다. 

 

 

자료를 보면 n * n! 이란 무시무시한 시간 복잡도가 나온다.

 

 

시간 복잡도

 

사실 보고정렬의 시간복잡도는 의미가 없다.

이걸 알아보는것도 웃긴 게 내가 지금 학교에서 이걸 쓰고 있는데 2교시에 숫자 28개 돌려놓은걸 점심 먹고 5교시하는 동안 끝날기미가 보이지 않는다.

 

계속 돌아가는중

 

 

이렇게 정렬이 랜덤이기 때문에 숫자가 좀만 커지면 끝날 기미가 보이지 않기 때문이다.

 

평균 시간 복잡도 : O((n+1)!)

배열의 가능한 수열이 n! 개 있기 때문에 이러한 시간복잡도가 나온다.

 

최악의 경우 : 무한

배열이 무작위로 섞이기에 정렬되기 전에 컴퓨터 수명이 먼저 나갈 수 있다.

 

숫자가 늘어나면 늘어날 수록 시간이 n!로 늘어나기에 수열 100개 정도면 죽었다 깨어나도 정렬 안된다.

궁금할까 봐 정렬 시각화 링크도 달아놓는다.

 

https://www.youtube.com/watch?v=DaPJkYo2quc&ab_channel=TimoBingmann

---

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool is_sorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
}

void shuffle(int arr[], int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        swap(&arr[i], &arr[j]);
    }
}

void bogo_sort(int arr[], int n) { // Start Sort
    int cnt = 0;
    while (!is_sorted(arr, n)) {
        shuffle(arr, n);
        cnt++;
    }
    printf("cnt : %d\n", cnt);
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {  }; // Input array
    int n = sizeof(arr) / sizeof(arr[0]);

    srand(time(NULL)); 

    printf("Original array:\n");
    print_array(arr, n);

    bogo_sort(arr, n);

    printf("Sorted array:\n");
    print_array(arr, n);

    return 0;
}

---

그냥 Quick Sort , Tim Sort 쓰자

 

 

PYTHON 코드, 속도 부분에서 압도적 승리