정렬 알고리즘 - O(n^2) - 버블 / 삽입 / 선택

 

평균 수행 시간이 O(n^2)인 알고리즘

 

버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort)

• 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬됨

 

 

min 정렬 기준

• 선택 정렬 -> 배열 요소 중에 가장 작은 값 선택해서 뽑아와서 정렬 
• 버블 정렬 -> index 0-1 자리 비교 - 큰 값 1 자리로 -> 1-2 비교 - 큰 값 2로 -> 1번 수행할 때마다 가장 큰 값 맨 뒤로 정렬
• 삽입 정렬 -> 0-1 자리 비교해서 정렬된 상태에서, 추가로 하나하나 삽입해서 정렬하는 방식 -> 삽입 방법 : 이전 요소들과 비교 - 작으면 앞으로 - 크면 비교한 요소 뒤에 위치하도록 정렬  

 

3개의 정렬 방식 모두 수행 속도가 요소 n개에 의존하고, 그것을 n 번 반복해야 정렬 완료 - n의 제곱

 

 

---

 

Insertion Sort 구현해보기

• Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다.(손 안의 카드)
• 두 번째 요소부터 이전 요소들과 비교하면서 insert 될 위치를 찾아가며 정렬하는 알고리즘

 

 

 

 

10을 정렬하려고 할 때 [10]을 copy 해서 temp에 대입시켜 놓고 비교하는 방식이다.

 

복사해놓은 temp를 j-1번째 요소 값과 비교

 

10과 80의 위치가 변하는 것이 아닌 배열[3] 자리에 80 대입 // 배열 [ 2 ] 자리에 들어갈 애 비교

// 맞으면 temp를 아니면 그 자리에 [j-1] = 70 넣고 // 배열 [1] 자리에 들어갈 애 비교

 

---

 

정렬 메서드 생성

 

 

 

 

 

 

출력 메서드 생성

 

 

 

 

 

Test

 

 

 

 

반복 1 -> 50 80 정렬 

반복 2 -> 50 70 80 

반복 3 -> 10 50 70 80 

----

반복 -7 -> 10 20 30 40 50 60 70 80

 

---

 

풀이 안 보고 다시 풀어보기

 

 

 

 

 

정렬 메서드 만드는 부분

for로 배열 처음부터 count까지 / while로 j위치 찾기 / 찾은 j위치에 복사해놓은 temp 넣기

 

출력 메서드 만들고 

value [i]로 가져와서 count까지 출력

 

객체 생성 출력 테스트

배열 만들어주고 insertionSort 메서드 활용, count 숫자 유의 - 

0번째부터라고 생각해서 7 넣으면 안 됨. 0번째부터 맞는데 i <7 되면 6번째까지만 값을 받아와서 정렬됨

30은 아예 출력 X

 

 

---

 

review

정렬 알고리즘 - 버블 / 삽입 / 선택 
Bubble/ Insertion / Selection - Sort
필요한 상황에 맞춰 가장 효율적인 것 선택!

이번 문제에서는 삽입 정렬 알고리즘 Insertion Sort 실습
핵심 개념은 이미 정렬되어있는 배열의 요소들과 비교하며 위치를 찾는 점인 것 같다.
배열 i 번째 값을 복사해놓고 i-1번째 요소와 비교해가며 자리 찾기!

개념과 흐름은 이해가 되었지만 그것을 구현하는 것이 아직 어색하기도 하고 서툴다.
반복문, 조건문을 사용할 경우나 변수를 사용할 경우
그것이 무엇을 위한 목적인지 어떤 값을 반환받는 것인지 확실히 해주는 것이 중요하다. 
반복 연습과 반복문, 조건문, 변수의 이해가 더 필요하다!