알고리즘 _ 2주차 수업내용

Simple Sort Algorithm

 

데이터를 오름차순 또는 내림차순으로 정렬하는 기본적인 알고리즘

종류 : 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 등

 

1. 버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 요소를 비교하여 잘못된 순서라면 위치를 바꾸는 방식으로 동작합니다. 이 과정을 반복하여 가장 큰 값이 리스트의 끝으로 "버블"처럼 이동합니다. 

동작 방식:

• 리스트의 처음부터 시작하여 인접한 두 개의 값을 비교합니다.
• 잘못된 순서라면 두 값을 교환합니다.
• 이 과정을 리스트 끝까지 반복한 후, 가장 큰 값이 맨 끝에 위치하게 됩니다.
• 나머지 요소들에 대해 같은 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 1, 5, 6, 9]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

 

 

 

 

 

 

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트를 순차적으로 탐색하며, 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식입니다.

동작 방식:

• 두 번째 요소부터 시작하여 그 요소를 앞의 정렬된 리스트와 비교합니다.
• 적절한 위치에 삽입하여 정렬된 부분을 확장해 나갑니다.
• 리스트 끝까지 이 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 9, 1, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

 

 

3. 선택 정렬 (Selection Sort)

선택 정렬은 매번 남아 있는 리스트 중에서 가장 작은(또는 큰) 값을 선택하여 앞쪽부터 차례대로 위치를 정렬해 나가는 방식입니다.

동작 방식:

• 리스트에서 가장 작은 값을 찾아 첫 번째 요소와 교환합니다.
• 다음으로 두 번째 작은 값을 찾아 두 번째 위치와 교환합니다.
• 이 과정을 리스트의 끝까지 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [1, 2, 9, 5, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

요약:

• 버블 정렬: 인접한 요소끼리 비교하며 정렬.
• 삽입 정렬: 이미 정렬된 부분에 새로운 요소를 삽입하며 정렬.
• 선택 정렬: 남은 요소 중 가장 작은 것을 찾아 차례대로 정렬.

이 알고리즘들은 구조가 단순하고 구현이 쉬워서 학습용으로 적합하지만, 시간 복잡도가 O(n2)O(n^2)O(n2)이기 때문에 큰 데이터 세트에는 비효율적일 수 있습니다.