버블정렬,선택정렬

알고리즘 자료구조/정렬

Zeta050525 2021. 8. 28. 23:29

728x90

도움 될만한것들

노마드코더

https://www.youtube.com/watch?v=Bor_CRWEIXo

나동빈님 영상과 노매드 코더 영상이 개인적으로 설명을 제일 쉽고 간결하게 해 주심

선택 정렬은 저기서 제일 작은 수를 선택합니다 그리고 0부터 시작해서 Index n 이랑 바꾸게 됩니다.

[5 3 2 1 7 8 10 9 6 4] > [1 3 2 5 7 8 10 9 6 4]

이런 식으로 바꾸게 됩니다.

한번 더 돌고 나면 3이랑 2랑 바뀌게 되겠죠?

Java로 구현해보면

이런 모습입니다

i for문은 배열의 길이만큼 반복을 하는 거고

j for문은 배열의 제일 작은 수를 찾기 위해 index n부터 끝까지 검사하는 역할을 합니다

한번 돌 때마다 시작하는 index의 위치가 n + 1로 바뀌게 되고

4번 돌았으면 4 + 1 5번째 인덱스부터 검사합니다

j for문을 보시면 100(배열에 든 수들보다 커야 함) 보다 작은 수는

bignum에 대입되고 ex) [6,7,4] 이런 배열이면

제일 처음엔 6이 담기고 그다음엔 5가 담기게 됩니다.

실행해보면

제대로 나옵니다.

똑같이 이런 배열이 있다고 하면

[5 3 2 1 7 8 10 9 6 4]

index n과 n +1의 값을 비교합니다 ex) 5 > 3

비교해서 n의 값이 더 크다면 둘을 스왑 해줍니다

롤에서 라인 스왑 할 때 똑같은 스왑이에요

별거 아니고 그냥 프로그래밍 기초 책 같은데 보면

두 개의 변숫값 교환하기 << 이거예요

이걸 index 0부터 끝까지 하는데

루프가 한번 끝나면 결국 제일 큰 수가 뒤로 가게 됩니다

[5 3 2 1 7 8 10 9 6 4] 이 배열에선 10이 맨 뒤로 가겠죠

즉 배열의 길이 - 1 만큼 해주면 된다는 겁니다

똑같이 자바로 짜 보면

위에서 말한 거처럼 Swap , Swap 또 Swap 합니다 그리고

i를 배열의 길이 - 1로 초기화해주고 1씩 감소시킵니다.

한번 i for문이 끝나면 어차피 제일 큰 수가 뒤로 가게 되니까요

-----------------------------------------------------------------------

아래 사진은 i for문 한번 돌고 난 후의 배열의 모습 //버블 정렬

728x90