정렬
-
[python]버블 정렬Programming/python 2019. 10. 20. 00:17
버블 정렬(Bubble sort)이란? 버블 정렬이란, 두 인접한 원소를 검사하여 정렬하는 방법이다. 거품 정렬이라고도 불리며 원소의 이동하는 모습이 거품이 수면으로 올라오는 듯한 것처럼 보이기 때문에 지어진 이름이다. 버블정렬의 특징 장점 구현이 간단하다. 단점 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 다른 요소들과 교환해야하는 필요 이상의 교환이 생긴다 시간 복잡도 시간 복잡도가 O(n²)로 상당히 느린편이지만 코드가 단순하기 때문에 자주 사용된다. 코드 #버블 정렬 #리스트 a를 버블 정렬로 정렬함 def bubble_sort(a): n = len(a) for i in range(0,n-1): for j in range(n-1): if a[j] > a[j+1]: a[j],..
-
[python]퀵 정렬Programming/python 2019. 10. 18. 22:46
퀵 정렬(Quick Sort)이란? 퀵 정렬은 기준(Pivot)을 먼저 정하고 그 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트들을 기준과 비교해 정렬한 다음 정렬된 부분을 합하는 방법. 그룹을 둘로 나누어서 재귀 호출한다는 방식은 병합 정렬과 비슷하지만 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다르다. 분할단계(divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽은 피벗보다 작은 요소들을 배치하고, 오른쪽은 피벗보다 큰 요소를 배치)로 분할한다. 정복단계(Conquer): 부분 배열을 정렬한다. 배열 크기가 충분히 작지 않다면 재귀 호출을 이용해서 다시 분할 정복 방법 적용(재귀는 리스트가 1이하가 될 때까지 반복된다) 결합단계(Com..
-
[python]합병 정렬Programming/python 2019. 10. 18. 01:52
합병정렬(Merge sort)이란? 합병정렬 또는 병합정렬이라고도 부르며, 먼저 절반으로 분할하고 합치면서 정렬하는 방법. 존 폰 노이만이 제안한 방법이며, 분할 정복 알고리즘의 하나이다. 리스트 길이가 1이하이면 이미 정렬된 것으로 본고 그렇지 않은 경우에는 분할단계(divide): 정렬되지 않은 리스트를 타노스 손가락 튕기듯이 절반을 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 마블 MCU로 생각하면 인피니트 워 단계 정복단계(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합단계(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 마블 MCU로 치면 앤드 게임에 해당한다. 오른쪽과 같이 [6,5,3,1,8,7,2,4]라는 정렬되지 않은 배열이 ..
-
[python]삽입 정렬Programming/python 2019. 10. 16. 01:39
삽입 정렬(Insertion sort)이란? 앞에 요소를 살펴보고 그 값보다 작은 지 큰 지를 비교해 적당한 위치에 삽입해서 정렬하는 방법. 리스트 중에 두 번째 요소를 key값으로 한다. 그 앞에 값과 키값을 비교한 뒤 작으면 그 앞, 크면 그 뒤에 넣는다. 그 다음 요소(세 번째)를 key값으로 한다. 그 앞에 값(두번째 요소)와 키 값을 비교한 뒤 작으면 앞 크면 그 뒤에 넣는다. 계속해서 반복한다. 직관적으로 이미지를 보면서 예를 들어보자면 다음과 같다. (a)옆에 [3,7,2,5,1,4]라는 배열이 있다. 가장 앞에 값인 3을 제외하고 두 번째 값인 7을 키 값으로 설정한다. 빨간색 박스는 key값이라는 뜻이다. 이 key값인 7은 3과 비교해서 더 큰 값이므로 3 뒤에 위치하게 된다. (b)다..
-
[python]선택 정렬Programming/python 2019. 10. 15. 00:16
선택 정렬(Selection sort)이란? 리스트 중에서 가장 작은 걸 선택한 뒤에 가장 앞으로 보내면서 정렬하는 방법. 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 값과 교체한다. 맨 앞의 값을 제외하고 다시 검색해서 최소값을 찾는다. 맨 앞의 값 뒤에 값과 최소값을 교체한다. 차례로 반복 직관적으로 애니메이션 이미지를 보면서 예를들어보자. 옆에 [8,5,2,6,9,3,1,4,0,7]이라는 배열이 있다. 가장 처음에 앞에서부터 찾아가며 최소값 0을 찾아내고 이를 맨 앞에 있는 0과 교환한다. [0,5,2,6,9,3,1,4,8,7] 그 다음에 0을 제외하고 검색을 시작하고 최소값 1을 찾아낸 뒤에 5와 1을 교환한다. [0,1,2,6,9,3,5,4,8,7] 그 다음에 0,1을 제외하고 검색을 시작하..