[2] Python 문제해결 - 정렬

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

정렬 과정

1. 첫 번째 원소부터 ㅇ니접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동

2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다.

3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품모양 같아서 버블 정렬이라고 한다.

< 슈도 코드 >

def BubbleSort(a) :

  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]

 

카운팅 정렬 : 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘

< 정렬 과정 >

1. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능하며 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 리스트를 사용하기 때문이다.

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

def CountingSort(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)