Tech Interview/Sorting4 정렬 알고리즘 표 (Python 코드포함) 인터뷰 대비를 위한 기본적인 정렬 알고리즘 표입니다. Python 버전의 코드 구현도 함께 비교할 수 있습니다. 클릭해서 보시는 것을 추천드립니다. 2021. 9. 17. [Python]Insertion Sorting 삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다. 장점은 N의 크기가 작을때 효과적이라는 것 단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2) 정리 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx def insertion_sort(a): n = len(a) for i in range(n): for j in range(i-1, -1, -1): if a[i] < a[j]: a[i], a[j] = a[j], a[i] i = j 2019. 5. 10. [Python]Selection Sorting i번째 인덱스를 최소값으로 선택하고, i+1부터 순회하면서 i보다 작은 값을 가진 인덱스 위치가 발견되면 swap 한다 장점은 구현하기 간단하고 비교 및 교환의 횟수가 버블, 삽입 정렬보다 적다는 특징을 가진다. 단점은 성능이 O(N^2)으로 좋지 않다. 정리 첫 인덱스부터 끝 인덱스까지 순회 Min Index 공간 1개 필요, 저장 현재 인덱스 값과 Min Index 스왑 def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1,len(arr)): if arr[j]< arr[min_idx]: min_idx = j arr[i],arr[min_idx] = arr[min_idx],arr[i] return arr 2019. 5. 9. [Python]Bubble Sorting 버블정렬은 거품이 올라오는 모양처럼 정렬한다고 해서 붙여진 이름이다. 장점은 구현하기 가장 간단하다는 특징을 가지고 있다 단점은 성능이 좋진 않다는 것. 평균 시간 복잡도 O(N^2) 정리 인접한 값과 비교 후 교환 스와핑 위한 공간 1개 필요 총 n-1번 루핑 def bubble_sort(arr): for _ in range(len(arr)-1): for j in range(len(arr)-1): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] return arr 2019. 5. 9. 이전 1 다음 728x90 반응형