본문 바로가기

공부/자료 구조 및 알고리즘

공부/자료 구조 및 알고리즘 2022. 10. 25. 퀵정렬 (Quick Sort) - python def partition(arr, start, end): pivot = start greater = start + 1 less = end while greater = end: return k = partition(arr, start, end) quickSort(arr, start, k - 1) quickSort(arr, k + 1, end) arr = [31, 53, 75, 42, 15, 64, 31] #정렬할 배열 print("[정렬되지 않은 배열]") print(arr) print() start = 0 end = len(arr) - 1 quickSort(arr, start, end) print("[정렬 완료된 배열]") print(arr) [정렬되지 않은 배열] [31, 53, 75, 42, 15, ..
공부/자료 구조 및 알고리즘 2022. 10. 25. 병합정렬 (Merge Sort) - python def merge(arr, start, mid, end): temp = [None] * len(arr) i = start j = mid + 1 k = start while i
공부/자료 구조 및 알고리즘 2022. 10. 25. 삽입정렬 (Insertion Sort) - python arr = [31, 53, 75, 42, 15, 64, 31] print("[정렬되지 않은 배열]") print(arr) print() for i in range(1, len(arr)): Index = arr[i] #index는 해당 삽입장소에서 대기 j = i - 1 #j는 삽입이 될 수도 있는 수 while (j >= 0 and arr[j] > Index): #정렬이 된 상황에서 true arr[j + 1] = arr[j] j -= 1 arr[j + 1] = Index print("[정렬 완료된 배열]") print(arr) [정렬되지 않은 배열] [31, 53, 75, 42, 15, 64, 31] [정렬 완료된 배열] [15, 31, 31, 42, 53, 64, 75]
공부/자료 구조 및 알고리즘 2022. 10. 25. 버블정렬 (Bubble Sort) - python #마이 에디션 arr1 = [31, 53, 75, 42, 15, 64, 31] print("[정렬되지 않은 배열]") print(arr1) print() n = len(arr1) for i in range(0, n): for j in range(0, n-i-1): if (arr1[j] > arr1[j+1]): arr1[j+1], arr1[j] = arr1[j], arr1[j+1] print("[정렬 완료된 배열]") print(arr1) print() #교수 에디션 arr2 = [86, 12, 54, 29, 65, 43, 23] print("[정렬되지 않은 배열]") print(arr2) print() n = len(arr2) for i in range(1, n): for j in range(1, n):..
공부/자료 구조 및 알고리즘 2022. 10. 24. 선택정렬 (Selection Sort) - python arr = [31, 53, 75, 42, 15, 64, 31] print("[정렬되지 않은 배열]") print(arr) print() for i in range(len(arr)): minIndex = i for j in range(i+1, len(arr)): if arr[minIndex] > arr[j]: minIndex = j arr[i], arr[minIndex] = arr[minIndex], arr[i] print("[정렬 완료된 배열]") print(arr) [정렬되지 않은 배열] [31, 53, 75, 42, 15, 64, 31] [정렬 완료된 배열] [15, 31, 31, 42, 53, 64, 75] 1. 배열 arr[0~n]에서 가장 큰 원소 찾기 2. 이 원소와 배열 끝의 arr[n]은 ..
자료의 정렬 - 합병 정렬(Merge sorting)
공부/자료 구조 및 알고리즘 2019. 8. 4. 자료의 정렬 - 합병 정렬(Merge sorting) 합병 정렬(Merge sorting) 서로 다른 두 집합을 하나로 합치는 정렬 방식. 전체 원소를 하나의 단위로 분할한 뒤 다시 병합(merge)하면서 정렬된다. 합병정렬(Merge sorting)의 방법 ① 모든 그룹의 자료를 2개의 그룹으로 분할한다. ② 그룹 내의 자료가 1이 될 때까지 계속 분할한다. ③ 분할이 끝나면 두 그룹에서 가장 앞에 있는 자료의 크기를 비교해 작은 자료부터 먼저 정렬한다. ④ 두 그룹의 자료들이 크기 순으로 정렬될 때까지 반복하여 하나의 그룹으로 만든다. ⑤ 다시 남은 그룹에 대해 같은 방법을 수행한다. ⑥ 하나의 그룹으로 만들어지면 정렬이 완료된다. 합병정렬(Merge sorting)의 예시 1. 3, 7, 2, 5, 1, 4를 합병정렬을 이용하여 배열해보자. 그룹 내의..
자료의 정렬 - 선택 정렬(Select sorting)
공부/자료 구조 및 알고리즘 2019. 7. 30. 자료의 정렬 - 선택 정렬(Select sorting) 선택 정렬(Select sorting) 나열된 숫자들 중 작은 순서대로 찾아서 왼쪽으로 정렬하는 방법. 최소값을 찾아 맨 앞으로 이동시키는 단순한 정렬 방법이다. 선택정렬(Select sorting)의 방법 ① 주어진 리스트중에서 최소값을 찾는다. ② 그 값을 맨 앞에 위치한 값과 교체한다. ③ 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 선택정렬(Select sorting)의 예시 1. 20, 7, 12, 8을 선택정렬을 이용하여 배열해보자. 위 숫자를 배열해보자. 가장 작은 항목을 찾아 첫 번째 숫자와 비교하고 자리를 바꾼다. 가장 작은 항목을 찾아 두 번째 숫자와 비교하고 자리를 바꾼다. 가장 작은 항목을 찾아 세 번째 숫자와 비교하고 자리를 바꾸려고 했지만, 세 번째 숫자가 더 작..
자료의 정렬 - 버블 정렬(Bubble sorting)
공부/자료 구조 및 알고리즘 2019. 7. 28. 자료의 정렬 - 버블 정렬(Bubble sorting) 버블 정렬(Bubble sorting) 나란히 있는 두 개의 데이터를 계속하여 바꾸어 나가면서 차례대로 정렬하는 방법이다. 정렬이 진행되는 모양이 비누 거품(bubble)과 같다고 하여 붙여진 이름. 버블정렬(Bubble sorting)의 방법 ① 두 개의 데이터를 계속하여 바꾸어 나가면서 차례대로 정렬하는 방법 ② 두수를 비교하여 가장 큰 수를 맨 오른쪽에 배치한다. ③ 큰 수를 오른쪽으로 이동 버블정렬(Bubble sorting)의 예시 1. 20, 7, 12, 8을 버블정렬을 이용하여 배열해보자. 위 숫자를 배열해보자. 처음 두 개를 비교해 교체한다. 다시 두 번째 세 번째를 비교해서 교체한다. 다시 세 번째 네 번째를 비교해서 교체한다. 이렇게 끝까지 가면 가장 큰 수가 맨 뒤로 가게 된다. 다시..
자료의 정렬 - 퀵 정렬(Quick sorting)
공부/자료 구조 및 알고리즘 2019. 7. 28. 자료의 정렬 - 퀵 정렬(Quick sorting) 퀵 정렬(Quick sorting) 피벗(pivot)을 기준으로 분류만을 통해 정렬을하는 방법. -피벗(pivot)이라고 부르는 기준을 필요로 함. -그 기준을 이용해 그 기준보다 작은 수들의 그룹과 그 기준보다 큰 수들의 그룹으로 나눈다. -일반적으로 왼쪽에서 오른쪽으로 가면서 피벗보다 큰 수를 찾아가고 -오른쪽에서 왼쪽으로 가면서 피벗보다 작은 수들을 찾아 서로 자리를 바꾼다. 퀵정렬(Quick sorting)의 방법 ① pivot을 선정하여 pivot을 기준으로 좌측과 우측으로 ② 왼쪽→오른쪽으로 가면서 pivot보다 큰 값을 찾고, 오른쪽→왼쪽으로 작은값 찾기 ③ 두 값 교환→ pivot값과 작은 값 교환 ④ pivot 변경→ 왼쪽으로 오면서 작은 값이 pivot 바로 다음 값일때→ pivot과 ..

티스토리툴바