Day 06 - 선택 정렬, 버블 정렬(Quiz 20, 21 내용 포함)

= 선택 정렬, 버블 정렬

오늘은, 수업 시간에 들으면서 좀 멘붕이었던 정렬 두가지를 정리해보려 한다.
조금 어려웠던게, 선택이랑 버블 정렬을 정보처리기사 필기 볼 때 분명히 봤다. 이론으로 파악도 하고 있다.
하지만, 이걸 내가 식으로 만들어서 쓰려니까 정작 식으로 어떻게 만들어야할지 감이 안와서, 수업을 듣는데 조금 스트레스를 받았다.
수업에 맞춰서 내실력이 쫓아가질 못하니까 마음은 급급하고, 또 완벽히 해내고는 싶구 ㅜㅜ 힘들다.

정렬 두개 정리하자~
실제로 선택정렬과 버블정렬을 식으로 나타내라고 하면, 아직은 모자라지만
그래도 전체적인 흐름은 잘 쫓아갈 수 있다!!

 

= 선택 정렬

끝 값은 똑같지만, 시작값이 하나씩 늘어나는 형태 (따라서 시작값 i+1)
선택정렬의 특징은, 자리에 맞는 값을 찾아서 있어야할 위치에 가져온다는 것~

<선택 정렬 예시문제>
중첩반복문을 이용해서 선택 정렬을 진행합니다.
int[]arr= {5,23,1,43,100,200,40};

<정답>
[1, 23, 5, 43, 100, 200, 40]
[1, 5, 23, 43, 100, 200, 40]
[1, 5, 23, 43, 100, 200, 40]
[1, 5, 23, 40, 100, 200, 43]
[1, 5, 23, 40, 43, 200, 100]
[1, 5, 23, 40, 43, 100, 200]

<해설>

반복 횟수를 length-1까지 사용하는 이유는, 마지막에는 어짜피 무조건 가장 큰 숫자가 차지할 것이기 때문에,
그 전까지 왼쪽에 작은수, 오른쪽에 큰 수가 위치하게 된다면 이미 전체가 순서에 맞게 배치되기 때문입니다.
여기서 중요한 건, temp를 활용했다는 것
수업시간에 들으면서 temp에 가 들어가야하는건지, j가 들어가야되는 건지 헷갈렸다.
잘생각해서 넣지 않으면 실수가 생기기 쉬울 부분이라는 생각이 들었다.

for(int j = i+1; j< arr.length;j++) { //모를때는 출력해보기 System.out.println(i+" - "+j); if(arr[i]>arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } System.out.println(Arrays.toString(arr));

+) 빠르게 오른차순으로 정렬할 수 있는 키.

미쳤다... 이거 보고, 정렬 공부를 해야하는가 심각하게 고민했음.

= 버블 정렬

선택 정렬과 같은데, 진행하는 과정이 다르기 때문에, 따로 정리가 필요하다.
버블 정렬은 ㅇ을 생각하면 된다, 배열에서 1, 2번째 위치한 수를 묶어서, 큰 수는 뒤로 빠지고, 작은 수는 앞으로 간다
배열에서 비교하는 수가, 인덱스의 순서로 표현하자면, (0,1), (1,2), (2,3) 이렇게 바로 이어진 수를 비교한다고 생각하면 편하다.

<버블 정렬 예시 문제>
정답은 선택 정렬과 같다.
int[]arr= {5,23,1,43,100,200,40}; -> 버블 정렬하기

<정답>
[5, 1, 23, 43, 100, 40, 200]
[1, 5, 23, 43, 40, 100, 200]
[1, 5, 23, 40, 43, 100, 200]
[1, 5, 23, 40, 43, 100, 200]
[1, 5, 23, 40, 43, 100, 200]
[1, 5, 23, 40, 43, 100, 200]

<해설>

선택 정렬과 다른 부분은, int i를 길이 -1 로 설정해서 바깥에 주어지는 반복이 비교할 대상의 회전 수를 나타낸다는 것.
비교대상은 나랑 내 다음친구! 그래서 j와 j+1를 두개 비교한다, 나보다 내 뒤에있는 애가 작다면 바꾸면 되니까!
여기서도 temp활용을 하는데, 나랑 내 다음에 있는 애가 위치를 바꾸다 보니까 i보다 j를 가지고 활용해서 문제를 풀게된다.

for(int i = arr.length-1;i>0;i--) {//6,5,4,3,2,1 for(int j =0; j<i;j++) { //여기서 한 번 출력을 해서 봐봐 무슨말인가~ //비교대상은 나랑 내 다음친구! 그래서 j와 j+1 //System.out.println(i+"-"+ j); if(arr[j]>arr[j+1]) { int temp = arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } System.out.println(Arrays.toString(arr));

 

선생님이 나중에 퀵정렬에대해서도 스스로 찾아서 학습했으면 좋겠다고 말씀하셨다.