[자료구조] 선택정렬/삽입정렬/퀵정렬 개념 및 예제 코딩

1. 선택정렬

전체 탐색으로 해서, 조건에 맞는 값을 찾으면, temp라는 변수를 사용해서,

2개를 swap 해가면서 탐색 및 정렬해가는 것이다.

쉽게, 간단한 배열을 선택 정렬로 구현한 예제이다.

 

2. 삽입 정렬

배열이나, 리스트의 끝원소부터, 차례로 작거나 큰값을 비교해 가면서 swap하는 방식

선택 정렬과 비슷하나, 점차 레인지를 줄여나가면서 하나씩 차례로 한다는 점에서 다르다.

 

 

3.퀵 정렬

 

기준 데이터를 설정하고, 기준보다 큰 데이터, 작은데이터의 위치를 바꾸는 것

가장 기본적인 퀵정렬은 첫번째 데이터를 기준 데이터 로 설정한다. (Pivot)

* pivot 값을 기준으로,-> 방향으로 탐색 해서, 큰값 <- 방향으로 해서 작은값 탐색

두개다 탐색이되면, 해당 두개를 swap해준다.이렇게 계속 swap을 해주다가

-> 와 <-의 교차지점이 생기면, 작은 값과 pivot의 위치가 바뀐다. 예를들어서 

 

5,4,7,8,9,6,1 의 배열을 퀵 정렬을 통해서 살펴보자

pivot은 5가 되고, 해당 작은값은 4, 큰값은 6이 처음 탐색에 걸린다. (큰수부터 오름차순의 경우, swap대상을 찾는거니까 반대로 생각하면 편하다.)

5,6,7,8,9,4,1  이렇게 변경이 된다. 이후에 한번더 동일하게 탐색을 한다.

-> 탐색은 4, <- 탐색은 9가 된다. 이때 교차 지점이 생기기 떄문에, 큰값과, 5의 위치를 바꿔준다.

그러면 6,7,8,9,5,4,1 이런식으로 pivot값이 정렬의 사이에 들어가게 된다.

이때 pivot을 대상으로 두개의 배열로 나눠 6,7,8,9  / 4,1 이런식으로 두개의 배열에 또 다시 퀵정렬을 가해주면 된다.

 

조금 복잡해보일수 있는데, 소스코드로 한번 보자

 

 

 

초기 배열의 크기는 파라미터로 넣어주고, 

추후에는 내부 변수에서 바꿔가면서 넣어준다.

기본 반복이기때문에 재귀이고, 재귀이기 때문에 제일 상단에, start,end에 대한 조건을 걸어주지않으면

무한히 돈다, 실행이 되지 않더라도, 함수가 함수를 호출하게된다.

 

stackoverflow 조심 ㅋ