정렬 알고리즘 (단순 교환, 선택, 삽입 정렬)

단순 교환 정렬 (비교횟수: n(n-1)/2))

• 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘. 버블 정렬이라고도 한다.

기본 버블 방식

뒤에 있는 원소부터 오름차순 정렬.

def bubble_sort(a):
	n = len(a)
    for i in range(n-1):
    	for j in range(n-1, i, -1):
        	if a[j-1] > a[j]:
        		a[j-1], a[j] = a[j], a[j-1]

=> 뒤에 있는 원소부터 제일 앞에 있는 원소까지 비교한다.

---

교환 횟수에 따른 정렬 방식

def bubble_sort(a):
	n = len(a)

    for i in range(n - 1):
        trade = 0
        for j in range(n - 1, i, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                trade += 1
        if trade <= 0:
            break

=> 원소 교환이 일어나지 않으면, 원소 교환 횟수가 0이면 정렬 중단

---

탐색 범위 제한하는 정렬 방식

def bubble_sort(a):
	n = len(a)

   while k < n-1:
   last = n-1
   for i in range(n-1, k, -1):
       if a[i-1]>a[i]:
           a[i-1], a[i] = a[i], a[i-1]
           last = i
   k = last

=> 특정 원소 이후 교환하지 않는다면, 범위를 좁혀서 비교,교환

---

쉐이커 정렬

def shaker_sort(a):
	left = 0
    right = len(a)-1
    last = rght
   
   	while left < right:
   		for i in range(right, left, -1):
           	if a[i - 1] > a[i]
               	a[i - 1], a[i] = a[i], a[i - 1]
                   last = i
        left = last
           
        for i in range(left, right):
           	if a[i] > a[i + 1]:
               		a[i], a[i + 1] = a[i + 1], a[i]
        			last = i
        right = last

=> 왼쪽으로 이동하며 큰수를 찾고, 오른쪽으로 이동하며 작은수를 찾는다.

단순 선택 정렬 (비교 횟수: (n^2-n)/2))

• 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

  def selection_sort(a):
  n = len(a)
  for i in range(n - 1):
  	min = i
     for j in range(i + 1, n):
     	if a[j] < a[min]:
         	min = j
     a[i], a[min] = a[min], a[i]

  => 아직 정렬하지 않은 부분에서 값이 가장 작은 원소를 선택
=> 가장 작은 원소와 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환

단순 삽입 정렬 (비교 횟수: n^2/2)

• 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘

  def insertion_sort(a):
  	n = len(a)
     
     for i int range(1, n):
     		j = i
         	temp = a[i]
         	while j > 0 and a[j - 1] > temp
         		a[j] = a[j - 1]
             	j -= i
         	a[j] = temp

---

이 세가지 단순 정렬 알고리즘의 시간 복잡도는 모두 O(n^2)으로 프로그램의 효율이 좋지 않다.