정렬 알고리즘 공부 (선택, 버블, 삽입, 퀵)

장성진·2020년 6월 13일
python알고리즘정렬
0
post-thumbnail

Sort

어느 순간 알고리즘 공부의 필요성을 느끼게 된 신입 개발자 입니다. 오늘부터 알고리즘은 조금씩 시간을 투자하여 공부하고 정리해보도록 해 볼려고 하는데요. 첫 번째 주제는 정렬 입니다. 앞서 다룰 정렬 예시는 모두 똑같은 문제로 진행되며 문제는 배열을 오름차순으로 정렬하는 것 입니다.

사용할 예시 데이터는 다음과 같습니다.

# 오름 차순으로 정렬 해라 
data = [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]

조금씩 제가 이해한 것을 한번 작성해보도록 해보겠습니다. 파이썬을 제대로 공부하고 시작하는 것이 아니고 알고리즘 공부와 파이썬의 기초정도를 같이 공부할 목적으로 시작하여 어느정도 이상한 부분, 비 효율적인 부분이 있을 수 도있습니다. 더 좋은 코드가 있으시면 알려주시면 감사하겠습니다.

선택 정렬 (Selection Sort)

첫번째 정렬이면서 가장 생각하기 쉬운편중 하나인 선택 정렬 입니다. 선택 정렬은 배열중에 가장 작은 숫자를 찾아서 맨 앞으로 보내고 다음으로 작은 수를 찾아서 그 다음으로 보내는 정렬 입니다. 예시는 다음과 같습니다.

  1. [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]
  2. [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]
  3. [1, 2, 10, 3, 7, 8, 5, 4, 9, 6]
  4. [1, 2, 3, 10, 7, 8, 5, 4, 9, 6]
  5. [1, 2, 3, 4, 7, 8, 5, 10, 9, 6]
    ....
    [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

위와 같이 정렬이 진행됩니다.

선택 정렬의 시간복접도는 O(N^2)로 상당히 비 효율적이고 빠르지는 못한 정렬중 하나 입니다.

이제는 코드로 어떻게 작성하는지를 확인해 보겠습니다.

data = [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]


for i in range(0, 10):
	min = 100000 # 제일 큰 수 또는 임시의 큰 수
	for j in range(i, 10):
		if min > data[j]:
			min = data[j]
			index = j
	temp = data[i]
	data[i] = data[index];
	data[index] = temp

이런식으로 코드를 작성할 수 있겠네요.

소스 코드는 간단한 편인거 같습니다.

버블 정렬 (bubble Sort)

다음 정렬은 버블 정렬 입니다. 버블 정렬도 앞서 말한 선택 정렬과 같은 시간 복잡도를 가지고 있습니다.(O(N^2)) 하지만 같은 시간 복잡도를 가지고 있다고 하여도 실제로 속도가 같은 것은 아닙니다. 심지어 첫 번째 정렬인 선택 정렬 보다도 느리다는 것 입니다. 같은 시간 복잡도지만 더 느린 버블 정렬의 동작 방식을 설명하겠습니다.

버블 정렬은 배열의 0번째 인덱스 부터 오른쪽으로 이동하면서 본인보다 작은 인덱스를 수색합니다. 예시를 한번 볼까요?

  1. [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]
  2. [1, 2, 10, 3, 7, 8, 5, 4, 9, 6]
  3. [1, 2, 3, 10, 7, 8, 5, 4, 9, 6]
  4. [1, 2, 3, 7, 10, 8, 5, 4, 9, 6]
  5. [1, 2, 3, 7, 8, 10, 5, 4, 9, 6]
  6. [1, 2, 3, 7, 8, 5, 10, 4, 9, 6]
  7. [1, 2, 3, 7, 8, 5, 4, 10, 9, 6]
  8. [1, 2, 3, 7, 8, 5, 4, 9, 10, 6]
  9. [1, 2, 3, 7, 8, 5, 4, 9, 6, 10]
  10. [1, 2, 3, 7, 5, 8, 4, 9, 6, 10]
  11. [1, 2, 3, 7, 5, 4, 8, 9, 6, 10]
    ....
    [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

어우 벌써부터 길죠...? 지금이야 10개의 데이터뿐이지만 만약 100개 1000개라고 생각해 봅시다... 분명 몇억 번 몇십억 번 까지 저 행동을 반복을 해야합니다.
이와 같이 정렬중에 많이 느린편에 속한 정렬을 코드로 한번 구현해 보겠습니다.


for i in range(0, 10):
	for j in range(0, 9-i):
		if data[j] > data[j+1]:
			temp = data[j]
			data[j] = data[j+1]
			data[j+1] = temp

위 코드와 같이 구현할 수 있습니다. 이미 언급한데로 같은 O(N^2)의 시간 복잡도를 가진 정렬중에 제일 느린 이유는 데이터 위치를 교체하는 코드가 제일 많이 실행되는것을 확인 하실 수 있습니다.

삽입 정렬 (Insertion Sort)

다음은 같은 시간 복잡도를 가진 정렬중에 가장 빠른편에 속하는 삽입 정렬입니다.

삽입 정렬은 어떤 식으로 작동할까요? 이름과 같이 삽입형태로 진행됩니다. 간단하게 설명하면 배열을 순회 하면서 본인보다 왼쪽 데이터가 작은 위치를 찾아 삽입 됩니다. 버블 정렬과 선택 정렬은 무조건 위치를 수정해가며 정렬을 하는데 삽입 정렬은 앞서 설명한데로 본인이 필요한 위치에만 이동하기 때문에 같은 시간 복잡도를 가져도 가장 빠른 정렬 방식이 될 수 있습니다. 가장 빠르다는 것은 같은 시간 복잡도를 가진 정렬안에서만 입니다.

이렇게 말로만 해서는 잘 모르겠지요? 다음 간단한 동작 예제를 봐볼까요?

  1. [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]
  2. [1, 10, 2, 3, 7, 8, 5, 4, 9, 6]
  3. [1, 2, 10, 3, 7, 8, 5, 4, 9, 6]
  4. [1, 2, 3, 10, 7, 8, 5, 4, 9, 6]
  5. [1, 2, 3, 7, 10, 8, 5, 4, 9, 6]
  6. [1, 2, 3, 7, 8, 10, 5, 4, 9, 6]
  7. [1, 2, 3, 5, 7, 8, 10, 4, 9, 6]
  8. [1, 2, 3, 4, 5, 7, 8, 10, 9, 6]
    ...
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

처음에는 버블 정렬과 비슷하긴 하지만 결국 왼쪽 기준으로 본인 위치를 찾아서 이동하는 모습을 확인 할 수 있습니다. 이것을 코드로 작성하면 어떻게 작성할 수 있을까요?

 for i in range(0, 9):
	j = i
	while data[j] > data[j+1]:
		temp = data[j]
		data[j] = data[j+1]
 		data[j+1] = temp
		j -= 1

이런식으로 코드를 작성할 수 있겠습니다. 삽입 정렬은 O(N^2)의 시간 복잡도를 가진 정렬중에 빠른거지 여전히 비 효율적인건 변하지 않았습니다. 하지만 특정 조건의 한에서는 정말 빠른 편일때가 있습니다. 특정 조건은 배열의 정렬 상태에 따라 많이 달라집니다.

퀵 정렬 (Quick Sort)

다음은 왠만한 정렬보다 빠른, 그리고 상당히 효율적인 방식을 이용하는 퀵 정렬입니다. 간단하게 말하자면 주어진 배열을 어떠한 기준으로 반으로 나눠서 두 집합으로 만든 후 정렬을 시작 하는데요 이때, 어떠한 기준은 피벗이라고 말합니다. 피벗의 기준은 보통 주어진 배열의 맨 앞, 첫번째 인덱스로 합니다. 간단하게 위에서 복습한 O(N^2)보다 효율적인 이유는 O(N^2)이고 N=10 일때 10 x 10 = 100으로 100번 검사를 한다고 했을때 퀵 정렬의 시간 복잡도는 O(N* logN)이고 퀵 정렬 일때는 반으로 쪼갠 후 정렬하기 때문에 (5 x 5 = 25) + (5 x 5 = 25) = 50이므로 앞서 설명한 버블, 삽입, 선택 정렬비해 효율적인 면이 많이 좋습니다.

이번에도 한번 어떤식으로 정렬이 되는지를 살펴 보겠습니다.

  1. [(1), 10, 2, 3, 7, 8, 5, 4, 9, 6]
  2. [1, (10), 2, 3, 7, 8, 5, 4, 9, 6]
  3. [1, (6), 2, 3, 7, 8, 5, 4, 9, 10]
  4. [1, (6), 2, 3, 4, 8, 5, 7, 9, 10]
  5. [1, (6), 2, 3, 4, 5, 8, 7, 9, 10]
  6. [1, (6), 2, 3, 4, 5, 8, 7, 9, 10]
  7. [1, (5), 2, 3, 4, 6, 8, 7, 9, 10]
  8. [1, (4), 2, 3, 5, 6, 8, 7, 9, 10]
  9. [1, (3), 2, 4, 5, 6, 8, 7, 9, 10]
  10. [1, 2, 3, 4, 5, 6, 8, 7, 9, 10]

위와 같이 정렬이 진행됩니다.

봐도 어떤식으로 진행되는지 어려우시죠? 저는 지금도 어렵습니다ㅠㅠㅠㅠ 위에 정렬되는 과정을 보시면 ( )안에 있는 부분이 피벗 즉, 기준입니다. 피벗 기준으로 오른쪽으로 본인보다 큰 숫자, 왼쪽으로는 본인보다 작은 숫자를 찾습니다. 그 후 오른쪽으로 찾은 큰 숫자와 왼쪽으로 찾은 작은 숫자가 엇갈리지 않았다면 찾은 큰 숫자와 작은 숫자의 위치를 바꿉니다. 그리고 피벗은 그대로 남습니다. 그 다음 또 반복을 하는데 오른쪽에서 찾은 큰 수와, 왼쪽에서 찾은 작은수가 엇갈릴때가 나옵니다. 그때는 찾은 큰 수와 작은 수 중 작은 수와 피벗의 위치를 바꿔줍니다. ( ex => 위 정렬 과정 중 1번 과정 입니다.)
이런 식으로 바꿔가면서 정렬 하는 방식이 퀵 정렬 입니다. 이제는 퀵 정렬을 Python 코드로 작성을 해보겠습니다.


number = 10;

def quickSort(array, start, end):
	# 원소가 1개일 경우
	if start >= end:
		return
	
        # 키는 첫번째 원소
	key = start
	i = start + 1
	j = end
	
	# 엇갈릴 때까지 반복
	while i <= j:
		# 키값보다 큰 값을 만날때 까지
		while i < 10 and array[i] <= array[key]:
			i += 1
		# 키 값보다 짝은 값을 만날 때까지
		while array[j] >= array[key] and j > start: 
			j -= 1
			
		# 현재 엇갈린 상태면 키 값과 교채
		if i > j:
			temp = array[j]
			array[j] = array[key]
			array[key] = temp
		else:
			temp = array[j]
			array[j] = array[i]
			array[i] = temp
			
	quickSort(array, start, j - 1)
	quickSort(array, j + 1, end)
	

quickSort(data, 0, number - 1)

위와 같이 코드는 조금 복잡 하지만 재귀 함수를 이용해서 작성할 수 있습니다.

결론 겸 느낌점

아직은 100% 이해하지는 못한 것 같지만 그래도 이런 정렬도 있다는 것을 인지하고 있는것과 인지 조차도 하지 못하는 것 과의 차이는 하늘과 땅 차이라고 생각하며 까먹지 않기 위해서 정리 겸 복습 겸 해서 포스팅을 작성해 봤습니다.

이 알고리즘을 공부하면서 python을 이용한 코드는 처음 작성해 보았습니다. { }가 없는 것이 아직은 적응이 안됐습니다. 하지만 이 알고리즘 정리를 하면서 더욱 익숙해 진 느낌 입니다.
python으로 작성을 하면서 위 알고리즘을 코드로 작성할때 필요했던 증감연산자가 없다는걸 알고 참 많이 놀랬습니다. 찾아보니 증감연산자의 역할을 하는 함수를 만든 코드들도 많이 있더라구요. 하지만 덕분에 증감연산자의 순서 중요성을 완전히 이해하지 못했다는것을 이번에 느끼고, 또 생각보다 좋은 기능 이였다는 것도 알았습니다. 이번 공부는 참 많은것을 느끼고 배운 유익한 시간이였습니다.

profile
장성진
많이 공부하고 싶은 개발자
이전 포스트

JAVASCRIPT ES7 ~ ES10 추가된 기능

0개의 댓글