반응형 알고리즘 기초3 [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort)이란? 리스트에서 하나의 피벗(Pivot)을 정하고, 이를 기준으로 피벗보다 작은 요소들, 피벗보다 큰 요소들로 두 개의 부분 리스트를 만들고(Divide : 분할), 정렬 후 다시 결합(Conquer : 정복)을 재귀적으로 반복하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 퀵 정렬(Quick Sort)의 특징 1. 주어진 배열(입력 배열) 이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다 3. .. 2021. 7. 19. [알고리즘] 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)이란? 앞(왼쪽)의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 삽입 정렬(Insertion Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 손 안의 카드를 정렬하는 방법과 유사하다. 5. 시간 복잡도는 Best : O(N), Avg : O.. 2021. 7. 18. [알고리즘] 버블 정렬 (Bubble Sort) 버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 검사하여 더 작거나 큰 값을 반복적으로 앞으로 보내는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 버블 정렬(Bubble Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중 구현 방법이 가장 간단하다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(N^2)이며 모든 정렬 중에 가장 비효율적인 정렬 .. 2021. 7. 18. 이전 1 다음 반응형
