[Python][이코테] 퀵 정렬
퀵 정렬 퀵 정렬은 이름대로 굉장히 빠른 정렬을 해주는 알고리즘이다. 또한 굉장히 많이 쓰인다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 이게 퀵 정렬의 기본이다. 과정 리스트 안에 있는 한 요소를 선택한다. 이를 피벗(pivot) 이라고 한다. 피벗을 기준으로 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈다. 먼저 사용된 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 기준으로 피벗을 각자 정해 다시 정렬한다. 나눠진 리스트들이 분할이 불가능할 때까지 반복한다. array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: #원소가 1개인 경우 종료 return p..
2022. 9. 13.
[Python][이코테] 삽입 정렬
삽입 정렬 삽입 정렬은 말 그대로 '삽입' 하여 정렬하는 것이다. 예를 들어 0~9까지 숫자를 오름차순 하고 싶은데 앞의 '선택 정렬'은 가장 작은 숫자를 '찾아서' 순서대로 맞춘다. 하지만 삽입 정렬은 일부러 찾는 것이 아닌 앞 인덱스와 비교하여 현재 인덱스 값 보다 앞 인덱스 값이 크면 '선택'하여 앞으로 보내는 것이다. 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(..
2022. 8. 31.
