버블 정렬, 선택 정렬

1. 정렬 알고리즘

• 정의) 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일

• 분류)
• 안정 정렬(Stable Sort) : 동일한 값들은 정렬 전의 위치 유지
• 버블 정렬, 삽입 정렬, 합병 정렬



• 불안정 정렬(Unstable Sort) : 동일한 값들이 정렬 후 순서가 바뀜
• 퀵 정렬, 선택 정렬, 힙 정렬

• 정리) 각각의 상황에 맞는 효율적인 방법 선택

2. 버블 정렬

• 정의) 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

• 과정)
• 앞에서부터 두 개씩 보며 두 수가 정렬되게 끔 자리를 바꿔줌
• 두 개씩 구간을 모두 훑고나서 정렬이 확정된 맨 마지막 자리는 다음 반복 땐 보지 않음
• 위 과정을 배열에 아무 변화가 없을 때까지 반복함
• 배열에 아무 변화가 없을 때 == 특정 루프의 전체 영역에서 swap이 한 번도 발생하지 않았을 때 (ex. i가 같을 때 swap 한 번도 안 한 경우)

• 예시) 6 5 3 8
• 5 6 3 8 → i=0, j=0
• 5 3 6 8 → i=0, j=1
• 5 3 6 8 → i=0, j=2 → {8}은 정렬 확정

---

• 3 5 6 8 → i=1, j=0
• 3 5 6 8 → i=1, j=1 → {6,8}은 정렬 확정

---

• 3 5 6 8 → i=2, j=0 → {3,5,6,8}은 정렬 확정

• 특징)
• 매번 반복할 때마다 가장 큰 수가 제일 뒤로 감 (오름차순 정렬 기준)
• 시간 복잡도 : 최선 O(N) , 평균 O(N^2) , 최악 O(N^2)

• 코드)

3. 선택 정렬

• 정의) 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방식

• 과정)
• 정렬 안 된 부분에서 최소값 또는 최대값을 찾고, 정렬 안 된 부분의 가장 앞에 있는 데이터와 swap
• 위 과정을 반복함

• 예시) 4 3 1 2
• 1 3 4 2 → {1}은 정렬 확정

---

• 1 2 4 3 → {1,2}은 정렬 확정

---

• 1 2 3 4 → {1,2,3,4}은 정렬 확정

• 특징)
• 매번 반복할 때마다 가장 작은 수가 제일 앞으로 감 (오름차순 정렬 기준)
• 시간 복잡도 : 최선 O(N^2), 평균 O(N^2) , 최악 O(N^2)

• 코드)

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main