본문 바로가기

Algorithm7

Bucket Sort 버킷 정렬 이건.. 맨 처음에 교재 보고 디용? 해서 그림으로 다시 정리하겠다.지금은 너무 졸림 왜 각 원소에 15를 곱하지..? 했더니 걍 원소의 개수(리스트의 길이)를 곱했던 것. def bucket_sort(arr): a = {} b = [int(i * len(arr)) for i in arr] for i in range(len(arr)): if b[i] in a: a[b[i]].append(arr[i]) else: a[b[i]] = [arr[i]] for k, v in a.items(): a[k] = insertionSort(v) a = sorted(a.values()) rslt = [item.. 2025. 10. 9.
Counting Sort_ 계수 정렬 알고리즘 앞에서 다뤘던 기수 정렬 알고리즘과 매우 유사하다.그래서 금방 풀었음참 신기한 방법일세 def counting_sort(arr): biggest = max(arr) cnt = [0] * (biggest + 1) for i in arr: cnt[i] += 1 for i in range(1, biggest + 1): cnt[i] += cnt[i - 1] rslt = [0] * len(arr) for item in arr: rslt[cnt[item] - 1] = item cnt[item] -= 1 return rslt최대값이 적당히 적으면 괜찮은데 max값이 3209519053182309이고 그러면 참 난감할 듯 싶다. 2025. 10. 9.
Radix sort(기수 정렬) 맨 처음엔 왜 카운트를 누적합으로 만들지?했는데놀라운 정렬방법이 있었슨~ def radix_sort(arr): d = len(str(arr[0])) for i in range(d): cnt = [0] * 10 for item in arr: cnt[item // 10 ** i % 10] += 1 start = [0] for j in range(1, 10): start.append(cnt[j - 1] + start[j - 1]) B = [1] * len(arr) for item in arr: B[start[item // 10 ** i % 10]] = item .. 2025. 10. 9.
Shell Sort 알고리즘 교재 보고 이해한 대로 작성한 코드def shell_sort(arr): num = 7 if len(arr) > 7 else 3 if len(arr) = 1] for i in step_list: for j in range(i): step_insertionSort(arr, j, i)def step_insertionSort(arr, k, step): for i in range(k + step, len(arr), step): #print(arr) new_item = arr[i] for j in range(i, k - 1, -step): if j == k or arr[j] > arr[j - step]: .. 2025. 10. 9.
Heap Sort 1년 전에 배웠던 자료구조 기억을 더듬어서...구현한 코드def print_heap(heap_array): ent = 1 cnt = 0 for i in range(1, heap_array[0] + 1): cnt += 1 print(heap_array[i], end=" ") if cnt == ent: print() ent *= 2 cnt = 0 print("\n-------------")def insert_maxheap(arr: list, n): if len(arr) == 0: arr.append(1) arr.append(n) return a.. 2025. 10. 8.
Quick Sort 알고리즘 def Quick_sort(arr, p, q): if q - p 맨 처음 개념을 이해하고 작성한 코드 여기에는 치명적인 오류가 있다.마지막 두 자리수가 정렬되지 않을 때가 있다는 것.. arr = [16, 77, 67, 31, 39, 25, 16, 47, 36, 46]오류가 생기던 리스트의 값을 넣고 디버깅을 해보겠다.리스트에 값이 2개 들어가도 정렬해야하는데 패스해버리는 바보같은 실수를 했다.if q - p 성공이다! partition함수가 지저분하게 느껴져서 교수님 코드도 봐보겠슴.. def quickSort(A, p:int, r:int, depth:int): if p int: x = A[r] # x: 기준 원소 i = p-1 # i: 1구역의 끝 지점 for j in ran.. 2025. 9. 27.

티스토리툴바