링크드 리스트 버블 소팅
알고리즘 1# 문제풀이
30대가 들어오면서, 아니 어쩌면 처음 취업을 하는 순간부터 '개발자의 정년은 언제인가?'라는 걱정과 고민을 했던 게 사실이다.
요즘 내린 결론은 자발적 은퇴의 시기는 '이제 그만 배우고 싶다'라는 마음이 들 때가 아닌가 생각한다.
그러던 중 우연히 회사에서 '알고리즘' 스터디를 한다길래 무작정 손들고 찾아갔다.
그리고 첫 시간.
우린 앞으로 hackerrank.com 에 있는 문제를 풀 것이며 컴퓨터나 종이 없이 머리로 생각하고 화이트보드에 문제를 풀기로 했다.
문제
아직 준비가 덜 된 우리를 위해서 출제된 첫 번 째 문제는 싱글 링크드 리스트를 만들고 그 안의 value를 오름차순 버블 소팅하여라.
싱글 링크드 리스트
버블 소팅
고민
싱글 링크드 리스트는 바로 알아 들었다.
Node 클래스를 하나 만들고 그 안에 변수로 다음 Node와 value를 갖게 만들면 될 거 같다.
그런데 버블 소트가 뭐지? 모르면 찾아보자. 거품 정렬.
https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
다행이다. 용어를 모를 뿐 동작원리라 구현 방법을 모르지는 않았다.
포인트는 swap이다. 앞/뒤를 비교해서 앞의 수가 뒤의 수보다 크면 교체를 하면 된다.
버블 소트 정렬
만약 4 2 8 6 1 의 수가 주어진다면 버블 소트로 풀이하면 이렇게 될 것이다.
2 4 8 6 1 : index = 0 ---- 시작
2 4 6 8 1 : index = 2
2 4 6 1 8 : index = 3 ---- 1 사이클
2 4 1 6 8 : index = 2 ---- 2 사이클
2 1 4 6 8 : index = 1 ---- 3 사이클
1 2 4 6 8 : index = 0 ---- 4 사이클
링크드 리스트의 swap
Node 가 4 개 존재할 때 n1, n2, n3, n4 중 n2와 n3 의 위치를 바꿔야 한다면?
이게 배열이면 n2와 n3 의 위치를 바꾸면 간단하다.
하지만 배열이 아니고 싱글 링크드 리스트다. 즉, 선후 관계를 앞의 노드들이 결정해 준다.
n2와 n3를 swap 하기 위해서는 n1 의 다음 노드를 n2 가 아니라 n3로 바꿔줘야 하고, n3 의 다음 노드는 n4 가 아니고 n2로 그리고 n2는 n4로 바꿔 줘야 한다.
기존 선행 관계 n1 -> n2 -> n3 -> n4를 다음과 같이 바꾼다.
n1 -> n3
n3 -> n2
n2 -> n4
구현
구현 코드는 미비하지만 github 에 올려놨다.
https://github.com/babosamo/algorithm-bubblesort
ps. fork & pull request 환영합니다.
ps2. 코드 지적, 다른 문제 풀이 더욱 환영합니다.
