정렬 및 연습문제

정렬 알고리즘

정렬 알고리즘이란, 불규칙적으로 나열되어 있는 값들을 일정 규칙으로 정렬하게 하는 알고리즘을 말한다. 쉽게 비유하면 줄을 맞춰서 세우는 것이다.

정렬 알고리즘은 쉽게 보면, 선택정렬과, 버블정렬이 있다. 그리고 여러 가지 정렬 등이 있지만, 그중 가장 많이 쓰이는 것이 퀵 솔트(Quick sort) 정렬이다.

퀵 정렬은 가장 활용성이 높고 좋아서, 많이 쓰인다. 쓰는 법은 65장 call back함수에서 나와 있으니 그렇게 알아두고, 선택정렬과 버블정렬을 알아보자.(퀵 정렬은 qsort( )인 선택정렬을 대신해주는 함수로 쓸 수 있다. 매개변수는 (배열이름, 크기, sizeof(자료형), 반환을 받는 함수)로 이루어졌으며, 반환함수에서 받은 값을 포인터로 강제 형변환 하고, 두 값을 서로 빼줘서 반환하게 하는 것이 65장에서 나오는 qsort( )의 사용방법이다. 복습하자.)

 

선택정렬, 버블정렬

두 정렬은 전에 배운, 최댓값 최솟값을 구하는 것과 비슷하다. (그리고 이번 면접시험에서 첫 번째로 나온 내용이다.)이 정렬의 핵심은 오른쪽의 for문과 네모 친 i, j의 선언에 있는데,

이것이 비교를 최소화하는 변수의

선언이다, 그렇게 비교를 해서, 크다면 작은 것이 저장된 정보를 바꿔서 이걸 요소만큼 반복하는 것이다. 여러 선택정렬을 하는 것들은 여러 가지가 있지만, 네모 친 것이 핵심이 되겠다. 그럼 선택정렬과 버블정렬의 차이점은 뭘까?

둘 다 비슷한 정렬 기법이다. 보통의 경우에 둘 다 같은 결과가 나오는데, 채워지는 과정에 차이점만 빼고 선택정렬과 버블정렬은 일치한다.

과정의 차이는 선택정렬은 앞으로 저장되고, 버블정렬은 뒤로 저장되는 것이다. (그래서 사실은 뒤로 가니까 버블정렬이 비효율적이다.) 그리고 평범히 했을 때는 선택정렬은 가장 작은 수를, 버블정렬은 가장 큰 수를 배열한다.(물론 거꾸로 구현하면, 큰 수, 작은 수가 바뀐다. 그래도 앞, 뒤로 빠지는 것은 변함없다.)

 

삽입정렬

삽입정렬은 임시변수를 만들어서, 차례차례 비교한 다음, 자신이 삽입될 인덱스에 삽입되는 정렬이다. (만약, 정렬의 요소들이 정렬대상보다 크면 뒤로 밀리면서 정렬대상이 들어갈 공간을 마련해 준다.)변수로 비교할 값을 담는 것이 차이점이다.

 

정렬 연습문제

- 연습문제 1

버블정렬에 대한 문제로, 사실 영상에 자료구조가 잘 나온다. 참고해서 이해한 후 코드로 잘 쓰기만 하면 된다. 기초적인 쉬운 문제다. 대신 동적할당을 받으라고 했으므로, 동적할당의 선언과, free로 메모리 해제까지 잊지 말고 해주면 된다.

- 연습문제 2

스택을 구현할 수 있는지를 묻는 문제로, 쉽지만 매우 중요하다. 스택구조는 지금까지 많이 해왔기에 코드를 이해만 하고 넘긴다.

- 연습문제 3

Call back함수와 qsort()함수의 문제로, 사실상 65장 문제다. 함수의 포인터라고 해서 다룬 내용이니 복습하는 김에, 새로 배운 내용도 접목해서 코드를 풀자.

(거의 다 왔다. 마지막까지 처음 배우는 마음으로 끝맺음을 짓도록 하자!)