1단계. 1의자리를 비교해서 정렬함(값이 같을때는 입력순서를 따름) 2단계. 10의자리를 비교해서 정렬 3단계. 100의 자리를 비교해서 정렬 시간복잡도 예제에서는 10진수의 수니까 N은 10임. 따라서 O(dn)의 수행시간을 가짐 자리수를 안다면 수행 성능은 O(32n) -> O(n)임

사전식정렬은 말그대로 사전에서 먼저 나오는 순서대로 정렬하는 것임 입력은 하나의 튜플인데 이게 key임 단계1에서 튜플의 맨마지막값을 비교해서 순서대로 정렬함. 4가 가장 작으니까 맨앞에 둠 단계2에서 중간값을 비교해서 크기순으로 정렬함 단계3에서는 첫번째 값을 비교해서 정렬하면 끝임 여기서 같은 값을 가질때는 입력순서에 따름 예제에서는 맨뒤부터 정렬했지만 맨 앞에서부터 정렬해도됨 어디부터 정렬할지 정하는것이 중요함

버킷 정렬 또는 버킷 소트(bucket sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬알고리즘이다. 각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다. key의 범위를 알려진 경우에만 사용가능한 정렬방식임 키의 값을 새로운 배열의 인덱스로 사용함 파이썬으로 구현해봄 1 2 3 4 5 6 7 8 9 10 11 12 13 def bucket_sort(keys, low, high): length = high - low + 1 # length of buckets bucket = [[] for _ in range(length)] keys_sorted = [] for elem in keys: bucket[elem-low].a..

정렬 중에서 퀵정렬에 대해서 알아보겠습니다. 2가지의 방식이 있습니다. 방법1. 1단계. 입력된 임의의 원소를 피벗으로 선택합니다. 피벗은 기준이 되는 원소입니다. 2단계. 피벗을 기준으로 작은 원소들, 피벗과 같은 원소들, 피벗보다 큰 원소들로 나눕니다. 3단계. 재귀적으로 정렬하고 크기순으로 놓으면 끝 파이썬으로 간단히 구현해보면 1 2 3 4 5 6 7 8 def quick_sort(S): if len(S) = b: return pivot_idx = random.randint(a, b) S[pivot_idx], S[a] = S[a], S[pivot_idx] pivot = S[a] left = a+1 right = b while left

리스트 분리해서 합칠때 정렬하는 방법입니다! 각각 재귀적으로 정렬을 수행하고 두개의 정렬된 배열을 합칩니다. 각각의 리스트의 맨 앞의 값을 비교해서 둘 중 작은 값을 새로운 리스트의 맨 앞에 삽입합니다. 파이썬으로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def merge_sort(L): n = len(L) if n

쉘 정렬(Shell sort)는 삽입 정렬에 전처리 과정을 추가한 것입니다. 전처리과정이란 작은 값을 가진 원소들을 앞쪽으로 옮겨서 큰 값들을 배열의 뒷쪽에 있게 하는 과정입니다. 전처리과정에서 일정한 간격으로 떨어진 원소들에 대해 삽입정렬을 수행합니다. 일정한 간격을 h-sort라고 합니다. 4-정렬은 인덱스0, 4, 8 한덩어리로 만들고 인덱스1, 5, 9를 한덩어리로 만들어서 수행하는 정렬입니다. 인덱스에 4를 더한것들을 모아서 한덩어리로 만드는겁니다. 그림에서 같은 색깔로 되어있는 부분이 한덩어리입니다. 같은 색깔내에서 삽입정렬을 수행합니다. 그러면 작은 값은 앞으로 큰 값은 뒤에 위치하게 됩니다. 이제 4-정렬에서 2-정렬로 바꿔서 다시 삽입정렬을 수행합니다. 그다음은 1-sort 결과적으로 정..

예를 들면, i인덱스의 값이 i-1값보다 작으면 i-1값과 자리를 바꾸고 i-2와 다시 비교하는 과정을 반복합니다. 이과정을 반복하다보면 전체적으로 정렬된 리스트를 얻게됩니다. 파이썬 코드로 간단히 구현해보았습니다. 1 2 3 4 5 6 7 def insertion_sort(L): for i in range(1, len(L)): for j in range(i, 0, -1): if L[j-1] > L[j]: L[j-1], L[j] = L[j], L[j-1] else: break cs 4번째 줄에서 비교를 하고 5번째 줄에서 교환을 합니다. 만약 j값이 j-1값보다 크다면 break문을 통해 다음 비교를 실행합니다. 다음은 삽입 정렬의 시간복잡도에 대해서 알아보겠습니다. 인덱스 1일때 인덱스 0과 한번 비교..

선택정렬(Selection sort): 배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘 1단계. 전체길이가 m일때 인덱스 0 ~ m-1 중에서 가장 작은 값을 찾아서 인덱스0의 값과 교환 2단계. 인덱스 1~m-1 중에서 가장 작은 값과 인덱스 1의 값을 교환 3단계. 이과정을 계속 반복하면 정렬된 리스트를 얻을 수 있다. 오름차순,내림차순 둘다 가능 선택정렬 파이썬 코드 1 2 3 4 5 6 7 def selection_sort(L): for i in range(0, len(L)): min_index = i for j in range(i, len(L)): if L[min_index] > L[j]: min_index = j L[..