정렬 알고리즘은 많이 사용하고있는 선택 정렬,삽입 정렬,퀵 정렬,계수 정렬 이정도가
많이 사용되고있다 그래서 이 4가지 방법을 다뤄볼려고 한다.
정렬 알고리즘을 공부를 통해 알고리즘의 효율의 중요성을 깨닫길 원한다.
1.선택 정렬(selection Sort)
데이터가 무작위로 여러개 있을때. 이중 가장 작은 데이터를 선택해서 맨앞에있는 데이터와 바꾸고,
그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다.
매번 "가장 작은 것을 선택"한다는 의미에서 선택 정렬이다.
코드 구현
array = [5, 1, 3, 7, 2, 9]
for i in range(array.__len__()):
minNum = i ## 제일 작은 인덱스 저장.
for j in range(i+1, array.__len__()):
if array[minNum] > array[j]:
minNum = j
array[i], array[minNum] = array[minNum], array[i]
print(array)시간 복잡도는 O(N^2)이다 . 굉장히 비효율적이다,하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.
2.삽입 정렬(Insertion Sort)
삽입정렬은 필요할 때만 위치를 바꾸므로'데이터가 거의 정렬되어 있을때' 정말 효율적이다.
코드 구현
array = [5, 1, 3, 7, 2, 9]
for i in range(len(array)-1):
for j in range(i+1, 0, -1): ## (start,end,step) end=0 이면 0까지 실행하는게아니라 1까지 실행함
if array[j] > array[j-1]:
break
array[j], array[j-1] = array[j-1], array[j]
print(array)
이것도 최악의 경우 시간 복잡도는 O(N^2)이다. 하지만 최선의 경우는 O(N)이다 배열이 거의 정리가 되있는 경우면 매우빠르게 정렬해준다.
3.퀵 정렬(Quick Sort)
퀵 정렬은 지금까지 배운 정렬 중에 가장 많이 사용중인 알고리즘이다.
퀵 정렬에서는 피벗pivot 이 사용된다.
코드 구현
array = [5, 3, 8, 4, 9, 1, 6, 2, 7]
def quick(array, start, end):
if start >= end:
return
pivot = start # 첫원소 피벗으로 지정
left = start+1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]: # 피벗보다 큰 숫자 나올때 까지 수행
left += 1
while start < right and array[right] >= array[pivot]:
right -= 1
if left > right: # 엇갈리면 피벗이랑 교환
array[right], array[pivot] = array[pivot], array[right]
else: # 안 엇갈렷으면 작은데이터와 큰 데이터 교환
array[right], array[left] = array[left], array[right]
quick(array, start, right-1)
quick(array, right+1, end)
quick(array, 0, len(array)-1)
print(array)
퀵 정렬은 평균적으로 시간 복잡도는 O(NlogN)이다,하지만 최악의 상황일때는 O(N^2)까지 갈수있다. 그런경우는 배열이 거의 정열이 된상태일때 그렇다.
4.계수 정렬(Count Sort)
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.계수 정렬은 최악의 경우 시간 복잡도가O(N+K)이다 하지만 조건이 있다
1.데이터 값이 다 정수여야한다 마이너스값이 들어가면 안된다.
2.일반적으로 가증큰 데이터와 가장 작은 데이터의 차이가 1,000,000 넘지 않을때 효과적으로 사용할수있다.
가장 큰 데이터와 가장 작은 데이터 차이가 너무 심하면 계수정렬을 안쓰는게 더 효과적이다.
array = [5, 2, 1, 5, 6, 1, 3, 8]
array2 = [0]*(len(array)+1)
for i in array:
array2[i] += 1
for i in range(len(array2)):
for j in range(array2[i]):
print(i, end=",")크기가 한정되있고 데이터 크기가 많이 중복되 있을수록 계수 정렬을 유리하며 항상쓰기엔 무리가 있다. 이런 조건만 만족한다면 계수 정렬은 매우 빠른 알고리즘이다.
