선택정렬, 삽입정렬 . 1

선택 정렬
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다

 

 

 

내가 쓰던 선택 정렬과 본질은 같지만 형태만 다른 코드

본질 :  0번째 인덱스에 가장 작은 수를 넣기

여기선 가장 작은 수가 있는 인덱스 번호를 찾는 방식이다

 

파이썬에서 변수 스와프 하는 방법

array[i],  array[min] = array[min],  array[i]

 

 

 

c++ 표준 라이브러리에서 제공하는 swap 함수

 

 

 

 

 

삽입 정렬
처리되지 않은 데이터를 하니씩 골라 적절한 위치에 삽입한다
(데이터를 하나씩 확인하면서 이 데이터가 어느 위치에 들어가는게 맞는지 매번 계산한다)
선택정렬에 비해 구현나이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다

 

 

 

 

 

i 번째 요소가 좌측으로 이동하며 맞는 위치를 찾고 그 위치에 삽입한다

 

 

 

 

자바는 포인터와 같은 기능을 제공하지 않고 별도로 표준 라이브러리에서 swap 연산을 제공하지 않기 때문에 

정석적으로 세 줄에 걸쳐서 swap을 한다

 

 

 

 

삽입 정렬은 데이터 형태에 따라 시간 복잡도가 달라진다.

이미 정렬되어 있는 상태의 데이터는 O(N) 의 시간 복잡도를 가진다