[C언어] 8가지 정렬 알고리즘

순차 정렬(Sequential Sort) 알고리즘

알고리즘

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

반복(i:=0->n)

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

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

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

 

 

본문 바로가기

---

버블 정렬 (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])

거품정렬 알고리즘

 

거품 정렬 구현

 

 

본문 바로가기

---

선택 정렬 (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

선택 정렬 알고리즘

 

 

선택 정렬 알고리즘 구현

 

 

본문 바로가기

---

삽입 정렬 (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

            아니면

                루프 탈출

 

 

본문 바로가기

---

쉘 정렬(Shell Sort) 알고리즘

쉘 정렬은 삽입 정렬 알고리즘을 이용하는 정렬 방식입니다.

쉘 정렬은 같은 간격에 있는 원소들을 삽입 정렬 원리로 정렬하는 것을 반복합니다.

간격의 초기값은 배열의 크기/2이며 간격이 1일 때까지 1/2로 줄이면서 반복합니다.

 

쉘정렬 알고리즘 진행 과정

본문 바로가기

---

퀵 정렬 (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)

 

본문 바로가기

---

병합 정렬(합병 정렬, 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

 

본문 바로가기

---

힙 정렬(Heap Sort) 알고리즘

알고리즘

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

초기 힙 구성

루트와 맨 마지막 자손 교환

    n을 1 감소

반복(n: n->1)

    힙 구성

    루트와 맨 마지막 자손 교환

    n을 1 감소

본문 바로가기