Quick 정렬

옛날에 공부했던거 ... 기억이 하나도 안난다 이래서 기록이 중요한가보다. 다시 공부하니 익숙하면서 새로운 이 기분...

Quick 정렬이란 ? 평균속도 N log N에 매우 빠른 정렬알고리즘 이다. 하지만, 최악의 경우에수 (수열이 완벽히 정렬되어 있을경우.) 에는 N*N 이 나오게 된다.

( 본 포스팅에 이용된 사진 출처 : https://www.youtube.com/watch?v=O-O-90zX-U4)

퀵 정렬은 특별한 값 기준으로 큰 숫자와 작은 숫자로 나눈다
이때 기준값을 pivot 값이라고 하고 이렇게 나누어서 하는 알고리즘을 분할 정복이라고 한다.

퀵 정렬은 일반적으로 가장 앞에있는 숫자를 피벗값으로 설정한다.

내림차순 정렬을 할 경우 3을 기준으로 좌측에서 기준값 보다 큰 값을 찾고 우측으로부터는 작은 값을 찾게된다.

이경우에는 좌측에서는 7 우측에서는 2가 된다

이렇게 값을 찾게됐다면 swap 을 해준다.

이렇게 계속해서 스왑하다가 엇갈리게 된다면 좌측에있는 값과 피벗값을 교체한다.

void quickSort(int *array, int start, int max) {
    
    if (max - start < 1) return; // 원소가 하나일경우 종료

    int pivot = start; // pivot index
    int i = start + 1; //좌측 index
    int j = max; //우측 index



    while (i <= j) {
        while (array[pivot] >= array[i] && i <= max) {// 중복 숫자 고려해서 >=
            i++;
        }

        while (array[pivot] <= array[j] && j >= start) { 
            j--;
        }
        if (j < i) { // 엇갈렸을때
            swap(array[pivot], array[j]);
        }
        else { // 엇갈리지 않았을때
            swap(array[i], array[j]);
        }
    }

    quickSort(array, start, j - 1);
    quickSort(array, j+1, max);        
}


int main()
{
    
    int length = 0;
    
    cin >> length;
    
    int* array = new int[length];


    for (int i = 0; i < length; i++) {
        cin >> array[i];
    }

    quickSort(array, 0, length-1);

    for (int i = 0; i < 10; i++) {
        cout << array[i];
    }
    return 0;
}

근데 이상하게 백준에서 안먹는다.

최악의 경우에수가 나온건가 ?

근데 영상강의에서는 되던대 ...

모르겟다 일단 이론만 알아가야겟다