[알고리즘 C언어] 2.2 순차 정렬(Sequential Sort) 알고리즘

이번에는 반복적인 방법으로 해결하는 순차 정렬(Sequential Sort) 알고리즘을 살펴볼게요.

 

정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 알고리즘을 말해요. 정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘이 필요합니다. 그리고 수행 후에는 배열 내의 자료들은 원하는 순서로 배치한 상태여야 합니다.

 

순차 정렬은 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 이를 위해 배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환해요.

순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=0->n)

        반복(j:=i+1->n)

            조건(compare(base[i], base[j]) > 0)

                교환(base[i],base[j])

예:

2 9 4 1 5 6 8 3 7       (정렬 전, n:9)

2 9 4 1 5 6 8 3 7       (i:0, j:1)

2 9 4 1 5 6 8 3 7       (i:0, j:2)

2 9 4 1 5 6 8 3 7       (i:0, j:3)

1 9 4 2 5 6 8 3 7       (i:0, j:3) – 교환

1 9 4 2 5 6 8 3 7       (i:0, j:4)

1 9 4 2 5 6 8 3 7       (i:0, j:5)

1 9 4 2 5 6 8 3 7       (i:0, j:6)

1 9 4 2 5 6 8 3 7       (i:0, j:7)

1 9 4 2 5 6 8 3 7       (i:0, j:8) – 1회전 완료

1 9 4 2 5 6 8 3 7       (i:1, j:2)

1 4 9 2 5 6 8 3 7       (i:1, j:2) – 교환

1 4 9 2 5 6 8 3 7       (i:1, j:3)

1 2 9 4 5 6 8 3 7       (i:1, j:3) – 교환

1 2 9 4 5 6 8 3 7       (i:1, j:4)

1 2 9 4 5 6 8 3 7       (i:1, j:5)

1 2 9 4 5 6 8 3 7       (i:1, j:6)

1 2 9 4 5 6 8 3 7       (i:1, j:7)

1 2 9 4 5 6 8 3 7       (i:1, j:8) – 2회전 완료

1 2 9 4 5 6 8 3 7       (i:2, j:3)

1 2 4 9 5 6 8 3 7       (i:2, j:3) – 교환

1 2 4 9 5 6 8 3 7       (i:2, j:4)

1 2 4 9 5 6 8 3 7       (i:2, j:5)

1 2 4 9 5 6 8 3 7       (i:2, j:6)

1 2 4 9 6 6 8 3 7       (i:2, j:7)

1 2 3 9 6 6 8 4 7       (i:2, j:7) – 교환

1 2 3 9 5 6 8 3 7       (i:2, j:8) – 3회전 완료

…생략…


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.

언제나 휴일 출판사의 수익금의 대부분은 아프리카에 기부하고 있습니다.

디딤돌 알고리즘 C언어는 디딤돌 자료구조와 알고리즘 with C언어에서 알고리즘 부분을 다루고 있어서 많은 부분에서 비슷합니다.


2.2.1 순차 정렬 알고리즘 성능 분석

2.2.2 순차 정렬 알고리즘 구현

2.2.3 순차 정렬 알고리즘 소스 코드