8가지 정렬 알고리즘/다양한 자료구조 구현 예제[C언어 소스]

“C언어 문법 책을 완독하고 이제 C언어는 익혔어.”라며 “다음은 무엇을 해야할까?”

처음 C언어로 입문한 이들이 한 번 쯤은 해 봄직한 상황이예요.

물론 시간이 지나고 20년 이상의 경력자가 되었을 때는 C언어를 익혔다는 표현은 쓰지 않을 거예요. 다만 필요한 곳에 사용할 뿐이죠.

암튼 프로그래밍을 학습하는 이들에게 문법 이후에 마주치는 것이 알고리즘과 자료구조일 거예요.

그 중에 8가지 정렬 알고리즘 다양한 자료구조를 코드로 표현하여 정리한 글들을 한 곳에 모았습니다.

알고리즘

순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
        반복(j:=i+1->n)
            조건(compare(base[i], base[j]) > 0)
                교환(base[i],base[j])

[C언어 소스] 순차 정렬(Sequential Sort) 알고리즘 시뮬레이션 구현하기

[C언어 소스] 버블 정렬 (Bubble Sort) 알고리즘

알고리즘

버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
        반복(j:=1; j<i ; j:=j+1)
            조건(compare(base[j-1], base[j]) > 0)
                교환(base[j-1],base[j])

[C언어 소스] 선택 정렬 (Selection Sort) 알고리즘

알고리즘

선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
        반복(max=0,j:=1; j<i ; j:=j+1)
            조건(compare(base[max], base[j]) < 0)
                max := j
        temp: = base[i-1]
        base[i-1] = base[max]
        base[max] = temp

[C언어 소스] 삽입 정렬 (Insertion Sort)

알고리즘

삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)
반복(i:=1; i<n ; i:= i+1)
        반복(j=i; j>0 ; j:=j-1)
            조건(compare (base [j-1], base [j]) < 0)
                temp: = base [j-1]
                base[j-1] = base [j]
                base[j] = temp
            아니면
                루프 탈출

[C언어 소스] 쉘 정렬(Shell Sort) 알고리즘

[C언어 소스] 퀵 정렬 (Quick Sort)

알고리즘

퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리)
조건(n<=1)
종료
피벗을 선택한다.
피벗과 맨 앞의 요소를 교환한다.
big:=0
    small:=n
    반복(big<small)
            반복(big:=big+1; big<n; big:=big+1)
                조건(compare(base[0],base[big])<0)
                    루프 탈출
            반복(small:small-1;small>0;small:small-1)
                조건(compare(base[0],base[small])>0)
                    루프 탈출
            조건(big<small)
                교환(base [big], base [small])
    교환(base [0], base [small])
    퀵 정렬(base,small, compare)
    퀵 정렬(base+big, n-big, compare)

[C언어 소스] 병합 정렬(합병 정렬, Merge Sort) 알고리즘

알고리즘

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
    ah:= n/2
    bh:= n – ah;
조건(n이 1보다 작거나 같으면) 종료
병합정렬(base,ah,compare)
    병합접열(base+ah,bh,compare)
    tbase에 동적 메모리 할당(원소크기*원소개수)
    메모리 복사(tbase,base)
ai:=0
    bi:=ah
    i:=0
반복(ai가 ah보다 작으면서 bi가 n보다 작다)
조건(tbase[ai]가 tbase[bi]보다 작거나 같으면
            base[i] := base[ai]
            ai:= ai+1
        아니면
             base[i]:= base[bi]
             bi:= bi+1
        i:=i+1
    반복(ai가 ah보다 작다)
        base[i]:= tbase[ai]
        i:=i+1
        ai:=ai+1
    반복(bi가 n보다 작다)
        base[i]:= tbase[bi]
        i:=i+1
        bi:=bi+1

[C언어 소스] 힙 정렬(Heap Sort) 알고리즘

알고리즘

힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
초기 힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
반복(n: n->1)
힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소