어느 때와 같이 구현되어 있는 sorting method를 사용하다가
갑작스럽게 내가 사용하고 있는 정렬알고리즘이 뭔지 궁금해졌다.
오잉? 처음 보는 녀석이 있네?
그래서 다른 정렬 알고리즘을 처음 봤을 때처럼 정렬 알고리즘을 시각화 한
유튜브https://youtu.be/kPRA0W1kECg?si=0FDdt9e72b3w3YVc를 봤다.
코드만 보는 것보다 이렇게 과정을 시각화해준 것과 함께 보는 것을 좋아하기 때문에 역시 좋다.
여기서 갑자기 안드로이드 어플리케이션으로 나만의 것을 한번 만들어 보자는 생각이 들었다.
일단 안드로이드 프로젝트를 만들고 라이브러리 추가를 해주었다.
dependencies {
implementation("androidx.lifecycle:lifecycle-viewmodel-compose:2.5.1")
implementation("androidx.compose.runtime:runtime-livedata:1.5.4")
// For additional google material icons
implementation("androidx.compose.material:material-icons-extended:1.0.0-alpha08")
...
}
컴포저블과 정렬 알고리즘을 연결해 줄 viewmodel과 livedata, 그리고 추가적인 구글 매터리얼 아이콘을 추가해주었다.
본격적으로 알고리즘을 만들어 주도록 하자.
일단 여러 정렬 알고리즘을 사용할 것이므로 그 들을 추상화한 인터페이스를 추가했다.
interface SortingAlgorithm<T: Comparable<T>> {
val displayInfo: String
suspend fun sort(arr: MutableList<T>, low: Int, high: Int)
}
정렬하려면 크기 비교는 당연히 돼야 할 것이므로 Comparable을 implementation하는 친구들만 다루자.
그리고 알고리즘에서 해당 리스트에 실제로 값을 업데이트하는 부분은 따로 구현해 주기로 했다.
첫 번째 예시인 QuickSort의 경우 swap 부분이 될 것인데 아래와 같이 만들어줬다.
interface Swap<T> {
suspend fun swap(arr: MutableList<T>, i: Int, j: Int)
}
Swap의 swap method를 보면 suspend로 되어 있는 것을 확인할 수 있다.
이 부분에 강제로 딜레이를 주지 않으면 알고리즘 연산 속도가 너무 빨라서 눈으로 확인하기 힘들기 때문에
딜레이를 주는 부분이 있기 때문에 설정해 주었다.
data class Element(
val value: Int,
val colorSwitch: Boolean = true
): Comparable<Element> {
override fun compareTo(other: Element): Int {
return if(value > other.value) 1 else -1
}
}
우리가 사용할 데이터 클래스이다. 리스트에 값을 업데이트하는 이벤트가 발생하는 동안
색을 바꾸어 주기 위해서 value 뿐만 아니라 colorSwitch로 색을 구분토록 하였다.
데이터 클래스와 swap이 만난 결과물이다.
class ElementSwap: Swap<Element> {
override suspend fun swap(arr: MutableList<Element>, i: Int, j: Int) {
arr[i] = arr[i].copy(colorSwitch = false)
arr[j] = arr[j].copy(colorSwitch = false)
Thread.sleep(10)
val temp = arr[i].copy()
arr[i] = arr[j].copy()
arr[j] = temp
arr[i] = arr[i].copy(colorSwitch = true)
arr[j] = arr[j].copy(colorSwitch = true)
}
}
색을 변경해 주고 눈으로 확인할 시간을 조금 주었다.
10이라는 값은 실험적으로 설정한 임의의 값이다. (노가다)
그리고 swap의 파라미터인 arr은 viewmodel에서 생성한 MutableStateList이다.
따라서, recomposition을 트리거하기 위해 값을 copy 해서 대입하는 모습이다.
위 3 인터페이스 및 클래스로 만들어진 것이 아래 QuickSort이다.
class QuickSort<T : Comparable<T>>(
private val _swap: Swap<T>
): SortingAlgorithm<T> {
override val displayInfo: String = QUICK_SORT_DISPLAY_INFO
override suspend fun sort(arr: MutableList<T>, low: Int, high: Int) {
if(low < high) {
val pi = partition(arr, low, high)
sort(arr, low, pi - 1)
sort(arr, pi + 1, high)
}
}
private suspend fun partition(arr: MutableList<T>, low: Int, high: Int): Int {
val pivot = arr[high]
var i = low - 1
for(j in low until high) {
if(arr[j] < pivot) {
i++
_swap.swap(arr, i, j)
}
}
_swap.swap(arr, i + 1, high)
return i + 1
}
}
혹시 Element와 다른 데이터 클래스를 혼용하여 사용할 가능성도 있다고 생각하여 DI로 swap을 넣어주었다.
다음 viewmodel을 보자.
class MainViewModel: ViewModel() {
private val _array = mutableStateListOf<Element>()
private val _algorithmName = MutableLiveData<String>()
val array: List<Element> = _array
val algorithmName: LiveData<String> = _algorithmName
private var _sortingAlgorithm: SortingAlgorithm<Element>? = null
val algorithmList = listOf(
QUICK_SORT_DISPLAY_INFO,
MERGE_SORT_DISPLAY_INFO
)
init {
init(QuickSort(ElementSwap()))
}
private fun init(sortingAlgorithm: SortingAlgorithm<Element>) {
_sortingAlgorithm = sortingAlgorithm
_algorithmName.value = _sortingAlgorithm?.displayInfo
_array.clear()
val temp = (1..NUM_DATA).toMutableList()
temp.shuffle()
temp.forEach {
_array.add(Element(value = it))
}
}
val onPlayButtonClickListener: () -> Unit = {
viewModelScope.launch(Dispatchers.IO) {
_sortingAlgorithm?.sort(_array, 0, NUM_DATA - 1)
}
}
val onAlgorithmClickListener: (String) -> Unit = {
when(it) {
QUICK_SORT_DISPLAY_INFO -> init(QuickSort(ElementSwap()))
MERGE_SORT_DISPLAY_INFO -> init(MergeSort(ElementInsert()))
}
}
}
값을 관리할 _array, 앱바에 현재 알고리즘의 이름을 노출할 _algorithmName,
현재 사용 중인 알고리즘인 _sortingAlgorithm을 준비해 주고
적당한 값의 상수 NUM_DATA[100]만큼 수열을 셔플해 _array에 대입해 주었다.
그리고 onPlayButtonClickListener가 불리면 sort를 수행하도록 하였다.
또한 알고리즘을 바꿀 녀석도 준비해 주었다.
디폴트는 QuickSort로 하고 이제 컴포저블을 구성해 주자.
@OptIn(ExperimentalMaterial3Api::class)
@Composable
fun MainComposable(
modifier: Modifier = Modifier,
viewModel: MainViewModel = viewModel(),
) {
val drawerState = rememberDrawerState(initialValue = DrawerValue.Closed)
val scope = rememberCoroutineScope()
val selectedItem = remember { mutableStateOf(viewModel.algorithmList[0]) }
ModalNavigationDrawer(
drawerState = drawerState,
drawerContent = {
ModalDrawerSheet {
Row {
Spacer(modifier = Modifier.weight(1f))
Box(
modifier = Modifier
.padding(12.dp)
.background(
color = MaterialTheme.colorScheme.secondaryContainer,
shape = CircleShape
)
) {
Icon(
modifier = Modifier
.size(80.dp)
.padding(12.dp),
imageVector = Icons.Filled.Architecture,
contentDescription = ""
)
}
Spacer(modifier = Modifier.weight(1f))
}
viewModel.algorithmList.forEach { algorithm ->
NavigationDrawerItem(
label = { Text(text = algorithm) },
selected = algorithm == selectedItem.value,
onClick = {
scope.launch { drawerState.close() }
selectedItem.value = algorithm
viewModel.onAlgorithmClickListener(algorithm)
}
)
}
}
},
) {
Scaffold(
modifier = modifier,
containerColor = MaterialTheme.colorScheme.primary,
floatingActionButton = {
FloatingActionButton(
onClick = viewModel.onPlayButtonClickListener
) {
Icon(imageVector = Icons.Filled.PlayArrow, contentDescription = "")
}
},
topBar = {
MainTopAppBar(
title = viewModel.algorithmName.observeAsState(initial = "").value,
menuButtonClickListener = {
scope.launch { drawerState.open() }
}
)
}
) {
Column(
modifier = Modifier
.fillMaxSize()
.padding(it)
) {
Spacer(modifier = Modifier.weight(1f))
Row(
modifier = Modifier
.fillMaxWidth()
.height(BOX_CONTAINER_HEIGHT.dp)
.padding(16.dp),
verticalAlignment = Alignment.Bottom
) {
viewModel.array.forEach { element ->
key(element.value) {
Box(
modifier = Modifier
.weight(1f)
.height((BOX_HEIGHT_COEFFICIENT * element.value).dp)
.background(
color = if (element.colorSwitch) {
MaterialTheme.colorScheme.primaryContainer
} else MaterialTheme.colorScheme.error
)
)
}
}
}
Spacer(modifier = Modifier.weight(1f))
}
}
}
}
@OptIn(ExperimentalMaterial3Api::class)
@Composable
fun MainTopAppBar(
title: String = "SAMPLE TITLE",
menuButtonClickListener: () -> Unit = {},
) {
TopAppBar(
title = { Text(text = title) },
actions = {
IconButton(onClick = menuButtonClickListener) {
Icon(imageVector = Icons.Filled.Menu, contentDescription = "")
}
},
colors = TopAppBarDefaults.smallTopAppBarColors(
containerColor = MaterialTheme.colorScheme.primary,
titleContentColor = MaterialTheme.colorScheme.onPrimary,
actionIconContentColor = MaterialTheme.colorScheme.onPrimary
)
)
}
알고리즘을 선택할 창을 위해 좌측 서랍하나 준비해 주고 서랍 상태 관리할 변수도 불러줬다.
Side sheet의 경우 탑앱바의 버튼을 누르면 나오도록 구성했다.
Scaffold의 버튼을 누르면 정렬을 시작하고 눈으로 관찰할 수 있게 되었다.
결과물을 보자.
오..ㅋㅋ 봐줄 만하다
MergeSort도 추가해 줬지만 기본적인 정렬 알고리즘의 구현부는 이곳에 적지는 않겠다.
이 글의 발단인 TimSort와 DualPivot QuickSort의 경우 다음글에서 알고리즘을 살펴보고
구현후에 동작을 확인하는 것까지 하는 것으로 하겠다.