Sorting Method

기본정렬(오름차순)의 몇가지 방법에 대해서 알아보자

코드는 C로 작성하였고 main함수는 다음과 같다.

0. main function

요소의 갯수를 입력받아 calloc함수를 통해 동적으로 배열을 할당하였다.

calloc앞에 (int*)형 변환을 하면 더 명시적이지만 없어도 상관은 없다.

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

swap함수를 매크로 설정 해놓는다. do while구문을 통해 매크로 안에서 변수를 선언할 수 있도록 했다.

1. Bubble sorting

개선된 형태의 bubble sorting

인덱스 K앞의 배열은 정렬이 완료 되었다. 가장 기본적인 형태의 bubble sort는 최악의 경우와 최선의 경우가 일치한다. 위의 코드 같은 경우에는 일반적인 형태에서 조금 더 발전된 형태로 이미 정렬된 배열에 대해서는 (n)의 시간 복잡도를 보인다.

//역 stable sorting이 되는 듯

2. selection sorting

최솟값을 탐색하여 정렬되지 않은 부분배열의 첫번째 요소와 교환한다.

탐색 방향에 따라서 안정된 정렬로 설계할 수 있다.

3. insertion sorting

요소를 하나씩 정렬된 배열의 맞는 자리에 삽입

안정된 정렬이다.

구현하는거 한 번 더 확인해보자.

위 3개의 정렬은 O(n^2)의 시간 복잡도를 가진다.

4. shell sorting

insert sorting의 응용된 버전으로 h만큼의 증분값에 따라 여러개의 배열로 나누어지고 그 배열에서의

5. quick sorting

좌측 포인터 pl, 우측 포인터 pr을 두고 그 가운데 중심 피벗 값 x를 둔다. 피벗 값을 기준으로 좌측은 피벗 값 보다 작은 값들 우측은 피벗 값보다 큰 값들을 둔다.

6. merge sorting

7. heap sorting

8. count sorting

9. Raidx sorting

YoungCode