알고리즘 종류 버블 삽입 선택 3가지 총정리

알고리즘에 대하여 아시나요 종류별로 정렬 알고리즘인 버블 삽입 선택 3가지에 대하여 자세하게 어떤 알고리즘인지 함께 알아보겠습니다.

 

알고리즘 버블

 

버블 정렬 알고리즘 버블 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 서로 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하는 방식으로 동작합니다. 정렬이 완료될 때까지 이러한 비교와 교환을 반복합니다. 이름은 정렬 중에 작은 값이 "올라가는(bubble)" 것과 관련이 있습니다. 알고리즘 동작 방식 기본 아이디어: 주어진 리스트의 처음부터 끝까지 반복하면서 인접한 두 원소를 비교하여 정렬합니다. 비교 및 교환: 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환합니다. 큰 값이 앞에 있어야 하는데 작은 값이 앞에 있다면 두 원소를 교환합니다. 한 단계의 반복: 한 번의 반복을 마치면 가장 큰 원소가 마지막 위치로 이동합니다. 모든 반복 수행: 위의 단계를 계속 반복하면서 리스트 전체가 정렬될 때까지 진행합니다. 시간 복잡도 버블 정렬의 시간 복잡도는 O(n^2)입니다. 최선의 경우(이미 정렬된 경우)에도 비교와 교환을 수행하기 때문에 성능이 좋지 않습니다.

 

삽입 알고리즘 무엇

 

삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 알고리즘 동작 방식 기본 아이디어: 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입합니다. 삽입 단계: 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입합니다. 삽입할 위치를 찾을 때까지 정렬된 부분의 원소들을 한 칸씩 오른쪽으로 이동시킵니다. 반복: 나머지 정렬되지 않은 부분에 대해서 위의 단계를 반복합니다. 모든 원소가 정렬될 때까지 진행합니다. 시간 복잡도 삽입 정렬의 평균 및 최악의 시간 복잡도는 O(n^2)입니다. 최선의 경우(이미 정렬된 경우)에는 O(n)의 시간 복잡도를 가집니다.

 

선택알고리즘

 

선택 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 최소값을 찾아 해당 값을 리스트의 맨 앞에 위치시키는 방식으로 동작합니다. 알고리즘 동작 방식 기본 아이디어: 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분에서 최소값을 찾아 정렬된 부분의 끝에 추가합니다. 선택 단계: 정렬되지 않은 부분에서 최소값을 찾습니다. 최소값을 정렬된 부분의 끝에 위치한 값과 교환합니다. 반복: 나머지 정렬되지 않은 부분에 대해서 위의 단계를 반복합니다. 모든 원소가 정렬될 때까지 진행합니다. 시간 복잡도 선택 정렬의 평균, 최악, 최선의 경우 시간 복잡도는 모두 O(n^2)입니다. 비교 연산과 교환 연산이 모두 n(n-1)/2 번 수행되기 때문에 비효율적입니다.