알고리즘에 대하여 아시나요 종류별로 정렬 알고리즘인 버블 삽입 선택 3가지에 대하여 자세하게 어떤 알고리즘인지 함께 알아보겠습니다.
알고리즘 버블
버블 정렬 알고리즘 버블 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 서로 인접한 두 원소를 비교하여 필요한 경우 위치를 교환하는 방식으로 동작합니다. 정렬이 완료될 때까지 이러한 비교와 교환을 반복합니다. 이름은 정렬 중에 작은 값이 "올라가는(bubble)" 것과 관련이 있습니다. 알고리즘 동작 방식 기본 아이디어: 주어진 리스트의 처음부터 끝까지 반복하면서 인접한 두 원소를 비교하여 정렬합니다. 비교 및 교환: 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환합니다. 큰 값이 앞에 있어야 하는데 작은 값이 앞에 있다면 두 원소를 교환합니다. 한 단계의 반복: 한 번의 반복을 마치면 가장 큰 원소가 마지막 위치로 이동합니다. 모든 반복 수행: 위의 단계를 계속 반복하면서 리스트 전체가 정렬될 때까지 진행합니다. 시간 복잡도 버블 정렬의 시간 복잡도는 O(n^2)입니다. 최선의 경우(이미 정렬된 경우)에도 비교와 교환을 수행하기 때문에 성능이 좋지 않습니다.
삽입 알고리즘 무엇
삽입 정렬은 간단하면서도 효율적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 알고리즘 동작 방식 기본 아이디어: 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분의 원소를 정렬된 부분에 삽입합니다. 삽입 단계: 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입합니다. 삽입할 위치를 찾을 때까지 정렬된 부분의 원소들을 한 칸씩 오른쪽으로 이동시킵니다. 반복: 나머지 정렬되지 않은 부분에 대해서 위의 단계를 반복합니다. 모든 원소가 정렬될 때까지 진행합니다. 시간 복잡도 삽입 정렬의 평균 및 최악의 시간 복잡도는 O(n^2)입니다. 최선의 경우(이미 정렬된 경우)에는 O(n)의 시간 복잡도를 가집니다.
선택알고리즘
선택 정렬은 간단하면서도 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 최소값을 찾아 해당 값을 리스트의 맨 앞에 위치시키는 방식으로 동작합니다. 알고리즘 동작 방식 기본 아이디어: 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 정렬되지 않은 부분에서 최소값을 찾아 정렬된 부분의 끝에 추가합니다. 선택 단계: 정렬되지 않은 부분에서 최소값을 찾습니다. 최소값을 정렬된 부분의 끝에 위치한 값과 교환합니다. 반복: 나머지 정렬되지 않은 부분에 대해서 위의 단계를 반복합니다. 모든 원소가 정렬될 때까지 진행합니다. 시간 복잡도 선택 정렬의 평균, 최악, 최선의 경우 시간 복잡도는 모두 O(n^2)입니다. 비교 연산과 교환 연산이 모두 n(n-1)/2 번 수행되기 때문에 비효율적입니다.
'IT가득' 카테고리의 다른 글
컴퓨터 용어 ssd hdd 차이점 알아보기 (1) | 2024.01.10 |
---|---|
데이터베이스 정규화 과정 용어 설명 알아보기 (0) | 2023.12.09 |
빅데이터 하둡 머신러닝 딥러닝 자세하게 it용어 총정리 (0) | 2023.12.09 |
클라우드 업체 BEST3 (아마존 구글 네이버) (1) | 2023.11.25 |
전산 3P에 관해 정보 총정리(사람 프로세스 플랫폼) (1) | 2023.11.25 |