정렬 알고리즘 - 수정

▼정렬(Sorting)

1)내부 정렬 : 데이터의 크기가 주기억장소 용량보다 적을 경우 기억장소를 활용하여 정렬하는 기법

ex) 버블 정렬(Bubble Sort)

     삽입 정렬(Insertion Sort)

선택 정렬(Selection Sort)

퀵 정렬(Quick Sort)

쉘 정렬(Shell Sort)

힙 정렬(heap Sort)

 

 2)외부 정렬 : 데이터의 크기가 주기억장소 용량보다 클 경우 외부 기억장치(디스크,테이프..)를 사용하여 정렬하는 기법

ex) 합병 정렬 (Merge Sort)

 

 

▼버블 정렬(bubble sort)

 :나란히 있는 두 개의 데이터를 계속해서 바꾸는 방식

 

1) list[i] > list[i+1] 이면 (i=0,1,2 ~ n-2)에 대하여 비교 후 바꿈

-> 가장 큰 값이 맨 뒤로 이동함

2) list[i] > list[i+1]  이면 (i=0,1,2,~ n-3)에 대하여 비교 후 바꿈

 -> 두 번째로 큰 값이 뒤에서 두 번째에 위치

.

.

n-1) list[i] >list [i+1] 이면 i=0 에 대하여 비교 후 바꿈

 

 

 

 

수행시간 복잡도 :

 

 

▼삽입 정렬(insertion sort)

 

 

j = 1,…,n-1에 대하여 각 단계에서 list[j]를 앞 방향으로 비교해가면서 교환해 나간다. 더 작은 값이 나오면 멈춘다.

처음 j=1,2,3…순서대로 진행을 하기 때문에 j번째 진행될때는 j-1개의 앞쪽 데이터는 정렬이 끝난 상태이다.

list[I]에 대하여 앞으로 진행하며 값을 찾아가는 과정이 된다.
- list[j]가 앞으로 이동하면서 list[j]보다 큰 데이터를 한 칸씩 뒤로 이동시킨다.

 

1) list[1]을 list[0]과 비교하여 만약 뒤 list[1] 데이터가 값이 더 작으면 바꾼다
(swap list[2]와 list[1])
    ->이 과정을 거치면 list[1], list[2]는 정렬된 상태가 된다.
2) list[2]을 list[1], list[0]과 순서대로 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1])

    ->이 과정을 거치면 list[i], i = 0,1,2는 정렬된 상태가 된다.
3) list[3]을 list[i], i = 2,1,0 순서대로 비교하여 만약 뒤 데이터가 값이 더 작으면 바꾼다
(swap list[i]와 list[i+1])
    ->이 과정을 거치면 list[i], i = 0,1,2,3은 정렬된 상태가 된다.
…
n-1) list[n-1]을 list[i], i = n-2,n-3,…,2,1,0 순서대로 비교하여 만약 뒤
데이터가 값이 더 작으면 바꾼다(swap list[i]와 list[i+1])
    ->이 과정을 거치면 list[i], i = 0,1,2,3,…,n-1은 정렬된 상태가 된다.

삽입정렬 프로그램의 각 단계별 첨자의 변화는 다음과 같다.
또 프로그램의 if 문에서 비교를 하게 되며 비교횟수(필요에 따라 교환)는아래와 같다.

(단계) (첨자 변화) (비교횟수)
1단계 : i=1 : j=0 1번
2단계 : i=2 : j=1,0, 2번
3단계 : i=3 : j=2,1.0 3번
… …
n-2단계 : i=n-2 : j=n-3,,…,2,1,0 n-2번
n-1단계 : i=n-1 : j=n-2,…,2,1,0 n-1번
각 단계에서 비교횟수는 비교 값보다 더 작은 값이 나오면 멈추므로 실제 더 작으나 최대를 가정한다.
따라서 정렬을 하기위한 전체 비교횟수 T(n) = n(n-1)/2 이다.
수행시간 복잡도 :  O(n(n-1)/2 ) = O(n2)이다.

 

 

▼퀵 정렬(quick sort)

 

1) 리스트에서 기준데이터(pivot value) 1개를 지정한 다음 리스트의 데이터들을 앞과 뒤 양쪽에서 가운데쪽으로 1개씩 비교하여 기준데이터보다 큰 값을 리스트 앞에서 찾아서 리스트의 뒤쪽으로, 기준데이터보다 작은 값은 리스트의 뒤쪽에서 찾아서 리스트의 앞쪽으로 둔다.

 양쪽에서 비교하여 오기 때문에 이동할 데이터를 찾으면 서로 맞 바꾼다. 이 과정이 끝나면 리스트는 자연스럽게 두개로 분리된다

(기준데이터보다 작은 값들, 큰 값들).
기준데이터는 리스트의 가운데 비교하여 오면서 만나는 위치에 둔다.

 

2) 첫번째 과정이 끝나면 두 개의 리스트(기준값보다 작은 리스트와 큰 리스트)에 대하여 각각 같은 방법으로 첫번째 과정과 같은 방법으로 분리한다. 기준값은 리스트에서 새로 정한다.

과정 2를 반복하면 나중에 데이터개수가 1개 있는 리스트가 남게 되며 이 때는 자동으로 정렬이 끝나게 된다.