Python02 :: sort

정렬(sort) 
오름차순, 내림차순 으로 정렬한것.

키란 자료를 정렬하는 기준이 되는 특정 값.

ex) 서류를 번호대로 정렬하기 - 키 : 서류번호

 

대표적인 정렬 방식의 종류

버블 정렬, 카운팅 정렬, 선택 정렬, 퀵정렬, 삽입 정렬, 병합 정렬 이 있다. 

버블 정렬과 카운팅 정렬 에 대해서 본다. 

 

버블 정렬 : 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

- 첫번쨰 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

- 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬됨

- 교환하며 자리를 이동하는 모습이 거품 모양과 같다고 해서 붙여짐

시간 복잡도 = O(n^2)

 

ex) 55, 7, 78, 12, 42를 버블 정렬하는 과정

맨앞에 두 숫자 55 7 을 비교한다

55가 크기 때문에 위치를 서로 바꾼다. 

7 55 78

그 다음으로 55와 78을 비교한다.

78이 더 크기 때문에 위치를 바꾸지 않는다. 

같은 방법으로 78과 12를 비교하여 위치를 바꾸고, 

78과 42를 비교하여 위치를 바꾼다. 이렇게 해서 첫번째 패스가 완료되면 

리스트의 맨마지막에 78이 배치되어 첫원소가 정렬이 완료된다. 

 

두번째 패스를 진행한다. 

앞단계에서 정렬된 것이 제외되기 떄문에 범위가 하나 줄어든다. 

55가 78의 앞자리에 배치된다. 

 

다음 세번쨰 패스 도 첫번째, 두번쨰 패스와 같이 비교한후 위치를 바꿔나간다. 

세번째 패스를 통과한후 42 55 78이 정렬이 완료된다. 

 

네번쨰 패스를 통과하면 4개의 숫자가 정렬되고 

마지막 패스에서 남은수가 하나이므로 정렬이 마무리 되며 모두 

숫자가 크기순으로 정렬된다.

7, 12, 42, 55, 78 으로 정렬된다.

 

버블 정렬을 수도 코드로 작성하면 다음과 같이 작성한다.

 

def BubbleSort(a) : # 정렬할 List

for i in range(len(a)-1, 0, -1) :

for j in range(0, i) :
    if a[j] > a[j+1]:

a[j], a[j+1] = a[j+1], a[j] 

 

안쪽 반복문의 제어가 밖의 반복문에 의해 제어되는것을 확인하기 바란다. 

 

카운팅 정렬, 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇개씩 있는지 세는 작업을 하여

선형 시간에 정렬하는 효율적인 알고리즘

 

하지만, 정수나 정수로 표현할 수 있는 자료에 대해서 적용가능.

이는 각 항목의 발생 회수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 리스트를 사용하기 떄문임.

, 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.

시간 복잡도 O(n+k) : n은 리스트의 개수, k는 정수의 최대값.

 

 0, 4, 1, 3, 1, 2, 4, 1 카운팅 정렬하는 과정을 예시 들어 설명.

일단, 데이터에서 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 리스트 COUNTS 저장

가장 큰수가 4이므로, 

0은 한번, 1은 세번, 2는 한번 3은 한 번 4는 두번

COUNTS LIST에는 1,3,1,1,2 가 저장된다.

 

정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 COUNTS의 원소를 조정

앞의 항목의 개수를 COUNT LIST 항목에 더하게 된다. 해당 원소가 정렬될때 리스트에 몇번 쨰 위치에 들어가야 하는지를 보여준다.

(그냥 누적한값)

 

이제, 데이터의 마지막 항목부터 원소를 정렬한다. 

마지막 원소가 1이므로 카운트 리스트에 1번 항목을 확인한다. 카운트 1의 값이 4임을 확인하고 1감소시키고

TEMP LIST의 4번쨰 칸에 1을 삽입한다. 

다음으로 4를 정렬해본다.(끝에서 두번째)

카운트 4의 값이 8임을 확인하고 1감소 시키고 TEMP LIST의 8번째 칸에 4를 삽입한다. 

다음은 2를 정렬한다. 카운트 2에 있는 값이 5임을 확인하고 1감소 시키고 이를 TEMP LIST의 5번쨰 칸에 삽입한다. 

같은 방식으로 1을 삽입한다. 카운트 1에 있는 값이 3임으로 1을 감소시키고 이를 TEMP LIST의 3번쨰 칸에 삽입한다. 

이어서 카운트 3 (=값 6) 을 5로 감소시키고 TEMP 6번쨰 자리에 3을 삽입한다. 

카운트 2 의 값을 감소시키고 TEMP에 1을 삽입한다. (감소되기 전에 INDEX로) 

DATA 4는 카운트 4번쨰 자리 7에서 6으로 감소시키고 TMEP  7번쨰 자리에 4를 삽입시킨다.(TEMP INDEX 시작은 1부터 인거같다.)

마지막으로 카운트 0을 감소시키고 TEMP에 0을 삽입한다. 

데이터 리스트에 마지막 원소까지 반복하면 temp list 에 값들이 정렬되어 저장되게 된다. 

 

* 수도 코드

def CoutingSort(A, B, k) :

#A [1 .. n ] -- 입력 리스트 사용된 숫자 (1~k)

#B [1 .. n ] -- 정렬된 리스트.

#C [1 .. k ] -- 카운트 리스트 

 

C = [0] * k

for i in range(0, len(B)) : 

C[A[i]] += 1

for i in range(1, len(C)):

C[i] += C[i-1]

for i in range(len(B)-1, -1, -1) :

B[C[A[i] -1 ] = A[i]

C[A[i]] -= 1

 

a = [0,4,1,3,1,2,4,1]

b = [0] * len(a)

CountingSort(a,b,5)

print(b)