버킷 정렬 또는 버킷 소트(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[..

회문 검사 회문(Palindrome): 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링 1. 전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교 2. 회문 검사하기는 주어진 스트링의 앞부분 반을 차례대로 읽어 스택에 push한 후 • 문자열의 길이가 짝수이면 뒷부분의 문자 1 개를 읽을 때마다 pop하여 읽어 들인 문자와 pop된 문자를 비교하는 과정을 반복 수행 •문자열의 길이가 홀수인 경우, 주어진 스트링의 앞부분 반을 차례로 읽어 스택에 push한 후, 중간 문자를 읽고 버린다. 3. 이후 짝수 경우와 동일하게 비교 수행 4. 만약 마지막 비교까지 두 문자가 동일하고 스택이 empty가 되면, 입력 문자열은 회문 파이썬 코드 1 2 3 4 5 6 7 8 9 10..

괄호 매칭 1.왼쪽 괄호는 스택에 push 2.오른쪽 괄호를 읽으면 pop 수행 3.pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 다른 종류이면 에러 처리, 같은 종류이면 다음 괄호를 읽음 4.모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면, 괄호들이 정상적으로 사용된 것 5.만일 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def is_matched(expr): lefty = '({[' righty = ')}]' S = Stack() #스택구현은 이전 글에 있습니다. for c in expr: if c in lefty: S.push(c) elif c in righty:..

스택(Stack): 한쪽 끝에서만 데이터를 삽입하거나 삭제하는 자료구조 데이터 삽입 연산: push 데이터 삭제 연산: pop 데이터 읽기 연산: top LIFO (Last-In First-Out): 마지막에 들어온 데이터가 먼저 삭제되는 방식 Stack을 코드로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Stack: def __init__(self): self._items = [] def __len__(self): #스택길이 return len(self._items) def __str__(self): return str(self._items) def is_empty(self): return self._items ..

이중연결리스트: 이중연결리스트(doubly linked lists)는 각 노드가 앞과 뒤를 가리치는 두 개의 레퍼런스를 가지는 연결리스트 단순연결리스트는 삽입이나 삭제할 때 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음 이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐 간단하게 이중연결리스트를 구현해보면 파이썬 코드 1 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5..