정렬 알고리즘

[정렬 알고리즘 이란?]

정렬(Sorting이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다.

 

정렬 알고리즘의 종류는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다.

 

7

5

1

2

4

6

3

 

위와 같이 각각의 수가 존재할 때 기본적으로 오름차순으로 수를 정렬한다면 아래와 같다.

1

2

3

4

5

6

7

 

내림차순 또한 마찬가지로 정렬한다면 아래와 같다.

7

6

5

4

3

2

1

 

이와 같이 우리는 특정한 수들이 존재할 때 정렬을 금방 수행할 수 있지만, 컴퓨터는 인간과 다르게 데이터의 규칙성을

 

직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.

 

[선택 정렬]

선택 정렬은 현재의 범위에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 과정을 반복하는 방식이다.

 

선택 정렬에 대한 설명과 예제는 아래의 게시물에서 확인할 수 있다.

https://unie2.tistory.com/23?category=873806 

선택정렬(Selection Sort)

 

[선택 정렬과 파이썬 기본 정렬 라이브러리 수행 시간 비교]

<선택 정렬 성능 측정>

from random import randint
import time

arr = []
for _ in range(10000) :
  arr.append(randint(1, 100))

start_time = time.time()

for i in range(len(arr)) :
  min_index = i
  for j in range(i+1, len(arr)) :
    if arr[min_index] > arr[j] :
      min_index = j

  arr[i], arr[min_index] = arr[min_index], arr[i]

end_time = time.time()
print("측정 결과 : ", end_time - start_time)

선택 정렬 성능 측정

 

<기본 정렬 라이브러리 성능 측정>

from random import randint
import time

arr = []

for _ in range(10000) :
  arr.append(randint(1, 100))

start_time = time.time()

arr.sort()

end_time = time.time()
print("측정 결과 : ", end_time - start_time)

기본 정렬 라이브러리 성능 측정

 

위 두 가지의 성능 측정 결과를 보면 기본 정렬 라이브러리를 사용하여 문제를 수행하는 것이 상대적으로 훨씬 짧은

 

시간에 정렬을 수행하는 것을 확인할 수 있다.

 

[삽입 정렬]

삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방식이다.

 

삽입 정렬에 대한 설명과 예제는 아래의 게시물에서 확인할 수 있다.

https://unie2.tistory.com/25?category=873806 

삽입정렬(Insertion Sort)

 

[퀵 정렬]

퀵 정렬은 기준 데이터를 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다.

 

또한, 퀵 정렬에서 사용되는 기준 데이터를 피벗이라 하며, 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지

 

미리 명시해야 한다. 

 

<퀵 정렬 예제>

arr = [5, 9, 7, 8, 4, 6, 2, 0, 1, 3]

def quick_sort(arr) :
  if len(arr) <= 1 :
    return arr

  pivot = arr[0]
  tail = arr[1:]

  left_side = [x for x in tail if x <= pivot] 
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(arr))

 

quick_sort( ) 메소드를 정의한다.

 

만약 리스트가 하나 이하의 원소만을 담고 있다면 종료처리를 수행해준다. 그렇지 않다면 변수 pivot 에 배열의 첫번째

 

원소를 할당해주고 변수 tail 에는 피벗을 제외한 리스트를 담아준다.

 

또한, tail의 값을 하나씩 확인하여 피벗값보다 작거나 같을 경우 변수 left_side에 할당해주고

 

tail의 값을 하나씩 확인하여 피벗값보다 클 경우 변수 right_side에 할당한다.

 

최종적으로 left_side를 매개변수로 하여 quick_sort( ) 메소드를 다시 수행한 것과 right_side를 매개변수로 하여

 

quick_sort( ) 메소드를 다시 수행하고, 전체 리스트를 반환한다.

 

[계수 정렬]

계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이며, 데이터의 크기 범위가

 

제한되어 정수 형태로 표현할 수 있을 때 사용한다.

 

또한, 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.

 

계수 정렬에 대한 설명과 예제는 아래의 게시물에서 확인할 수 있다.

https://unie2.tistory.com/31?category=873806 

계수 정렬(Counting Sort)