컴퓨터 공학 스터디 W1.자료구조와 알고리즘, 언어론👏
보고정렬이란?
보고 정렬이란 무엇일까? 아마 처음 들어보는 사람이 많을 것이라 예상된다.
보고 정렬이란 정렬을 해야하는 자료들을 랜덤으로 섞는 알고리즘이다.
순서
- 자료가 정렬되어있는지 확인한 후 정렬이 안되어있으면 랜덤으로 섞는다
- 정렬이 될때까지 계속 1번을 반복한다
말로만 했을 때는 '이게 뭔 알고리즘이지?' 라는 생각을 할 수 있다. 간단한 예시로 보고 정렬에 대해 설명해보겠다.
예시
이렇게 짱구, 유리, 훈이, 철수, 맹구가 있다. 이 친구들을 가나다 순으로 정렬을 해보려고 한다. 현재 상태는 정렬이 되어있지 않은 상태이기 때문에 랜덤으로 한 번 섞어본다.
자 이렇게 랜덤으로 한 번 섞어 보았다. 근데 순서는 훈이, 짱구, 맹구, 유리, 철수 순서이다. 가나다 순이라면 맹구가 첫번째에 와야하는데 마지막에 와야하는 훈이가 첫번째 순서에 와있다. 이러면 정렬이 되지 않은 것이므로 다시 랜덤으로 섞어야 한다.
한번 더 랜덤으로 섞어주었다. 하지만 이번에도 가나다 순으로 정렬이 되지 않았다. 이렇게 정렬이 될 때까지 계속 랜덤으로 돌려주는 정렬이 바로 보고 정렬이다.
예시를 통해서 살펴본 대로 계속 랜덤으로 돌려줘야 정렬이 된다. 이 정렬은 다른 이름으로 stupid sort, 멍청이 정렬이라고도 불린다.
시간 복잡도
이 정렬의 최선의 시간 복잡도는 Ω(n)이다. 최악의 시간 복잡도는 무한대라고 한다. 이 말은 아무리 랜덤으로 돌려도 정렬이 되지 않을 수도 있다는 뜻이다.
예제 코드
이번엔 예제 코드를 통해 설명해보겠다.
이 코드는 숫자 10개를 랜덤으로 정렬이 될 때까지 섞어주고, 정렬한 횟수까지 출력해주는 코드이다.
이 코드를 실행해보면 이렇게 나온다.
정렬이 되었다. 근데 정렬한 횟수가 약 780만번이다. 이렇게 예제 코드를 통해서 보니 정말 비효율적인 정렬이라는 것이 와닿을 것이다.
사용
이 정렬은 너무 비효율적이어서 잘 사용하지는 않는다고 한다. 그렇지만 효율성이 좋은 정렬(ex.선택정렬, 힙정렬 등)과 비교 용도로 사용된다고 한다.
