BubbleSort in Jetpack Compose

Merhaba sizlere bu yazımda veri yapılarında sıralama algoritmalarında gördüğümüz BubbleSort’u android cihazımızda nasıl programlayıp kullanabiliriz bunu anlatacağım. Biraz uzun bir yazı olacaktır.

Öncelikle bubleSort nedir?

Bubble sort, bir sıralama algoritmasıdır ve bir dizi elemanı küçükten büyüğe veya büyükten küçüğe doğru sıralamak için kullanılır. Adını, diziyi sıralamak için bir sonraki adıma geçmeden önce elemanları yerlerinde “yer değiştirerek” hareket ettirmesinden alır.

Bubble sort, adım adım çalışır. Her adımda, komşu iki eleman karşılaştırılır ve gerekiyorsa yer değiştirilir. Algoritma, dizideki tüm elemanlar sıralanana kadar bu işlemi tekrarlar.

İşleyiş şu şekildedir:

1. Dizi boyunca her eleman için, o eleman ve bir sonraki eleman karşılaştırılır.
2. Eğer bu iki elemanın sırası yanlışsa (küçükten büyüğe ise), yer değiştirilir.
3. Bu işlem dizinin sonuna kadar devam eder.
4. İlk geçişte en büyük (veya en küçük) eleman en sona (veya başa) yerleşir.
5. Bu adımlar, dizinin tamamı sıralanana kadar tekrarlanır.

Bu algoritmanın zaman karmaşıklığı O(n²) olup, büyük veri setleri için etkili değildir. Ancak, küçük veri setleri veya eğitim amaçlı olarak kullanılabilir.

Şimdi programlamaya geçelim :)

data class SortInfo(
  val currentItem:Int,
  val shouldSwap:Boolean,
  val hadNoEffect:Boolean
)

1. currentItem: Bu özellik, sıralama algoritmanızın mevcut adımında işlem gören elemanın değerini temsil eder. Yani, sıralama işlemi sırasında hangi elemanın değeri üzerinde işlem yapıldığını belirtir.
2. shouldSwap: Bu özellik, sıralama algoritmanızın mevcut adımında belirli bir elemanın yer değiştirmesi gerekip gerekmediğini belirtir. Yani, bu özellik, belirli bir adımda iki elemanın yer değiştirmesi gerekip gerekmediğini gösterir.
3. hadNoEffect: Bu özellik, sıralama algoritmanızın mevcut adımında yer değiştirme işleminin gerçekleşip gerçekleşmediğini belirtir. Eğer bu özellik true ise, o adımda herhangi bir yer değiştirme işlemi yapılmamıştır.

Bu SortInfo veri sınıfı, sıralama algoritmanızın adımlarını takip etmek ve gerektiğinde bilgi saklamak için kullanacağız.

data class ListUiItem(
  val id:Int,
  val isCurrentlyCompared:Boolean,
  val value:Int,
  val color: Color
)

1. id: Bu özellik, listedeki öğenin benzersiz bir tanımlayıcısını temsil eder. Her bir öğenin farklı bir id değeri olmalıdır.
2. isCurrentlyCompared: Bu özellik, sıralama algoritmanızın mevcut adımında ilgili öğenin karşılaştırılma durumunu belirtir. Yani, bu özellik, belirli bir adımda ilgili öğenin sıralamada işlem görmekte olduğunu gösterir.
3. value: Bu özellik, listedeki öğenin değerini temsil eder. Bu, sıralama algoritmasının gerçekleştirdiği sıralama işleminden önce ve sonra öğenin değeri olarak değişebilir.
4. color: Bu özellik, listedeki öğenin görsel arayüzündeki rengini temsil eder. Öğelerin renkleri, örneğin sıralama algoritmasının belirli adımlarında veya karşılaştırma durumlarında, kullanıcıya işlemlerin durumunu görsel olarak göstermek için kullanılabilir.

Bu ListUiItem veri sınıfı, sıralama algoritmanızın çalışmasını görsel olarak temsil etmek ve kullanıcıya sıralama işleminin ilerlemesini göstermek için kullanacağız.

class BubbleSortUseCase {

  operator fun invoke(list:MutableList<Int>) : Flow<SortInfo>  = flow{

    var listSizeToCompare = list.size-1
    while(listSizeToCompare>1){
      var innerIterator = 0
      while(innerIterator<listSizeToCompare){
        val currentListItem = list[innerIterator]
        val nextListItem = list[innerIterator+1]
        emit(
          SortInfo(currentItem = innerIterator, shouldSwap = false, hadNoEffect = false)
        )
        delay(500)
        if(currentListItem > nextListItem){
          list.swap(innerIterator,innerIterator+1)
          emit(
            SortInfo(currentItem = innerIterator, shouldSwap = true, hadNoEffect = false)
          )
        }else{
          emit(
            SortInfo(currentItem = innerIterator, shouldSwap = false, hadNoEffect = true)
          )
        }
        delay(500)
        innerIterator +=1
      }
      listSizeToCompare -= 1
    }
  }
}

fun <T> MutableList<T>.swap(indexOne:Int, indexTwo:Int){
  val tempOne = this[indexOne]
  this[indexOne] = this[indexTwo]
  this[indexTwo] = tempOne
}

1. BubbleSortUseCase sınıfı, listenin Bubble Sort algoritması kullanılarak sıralanmasını sağlar.
2. invoke işlevi, listenin sıralanmasını gerçekleştirir ve Flow dönüş tipinde bir akış oluşturur. Bu, sıralama işleminin her adımını yayınlamak için kullanılır.
3. İçteki flow kapsamı, sıralama işleminin gerçekleştirildiği yeri içerir. İlk olarak, listSizeToCompare değişkeni listenin boyutundan bir eksik olarak ayarlanır. Bu, sıralama işlemi sırasında karşılaştırma yapılacak eleman sayısını temsil eder.
4. İki while döngüsü kullanarak, listenin her elemanını sıralamak için iteratif bir yaklaşım kullanılır. İçteki while döngüsü, listenin içinde dolaşarak her elemanı karşılaştırır.
5. Her bir eleman karşılaştırıldığında, emit işlevi aracılığıyla ilgili adımın bilgileri bir SortInfo nesnesi olarak akışa yayılır. Bu, kullanıcı arayüzünde sıralama işleminin durumunu göstermek için kullanılır. Ayrıca, delay işlevi kullanılarak işlem adımları arasında bir gecikme sağlanır.
6. Eğer iki elemanın sırası yanlışsa (currentListItem > nextListItem), swap işlevi kullanılarak bu elemanların yerleri değiştirilir ve tekrar emit işlevi aracılığıyla bu değişiklikler akışa yayılır.
7. Eğer iki elemanın sırası doğru ise, emit işlevi aracılığıyla bu durum da akışa yayılır.
8. Her adımda içteki döngüler, listenin boyutunu azaltarak devam eder. Bu, her adımda listenin sonundaki elemanların sıralama işlemine dahil edilmemesini sağlar.

Bu şekilde, BubbleSortUseCase sınıfı, bir liste üzerinde Bubble Sort algoritmasını uygulayarak sıralama işleminin her adımını yayınlayan bir akış oluşturur.

class SortViewModel(
  private val bubbleSortUseCase: BubbleSortUseCase = BubbleSortUseCase()
) :ViewModel() {

  var listToSort = mutableStateListOf<ListUiItem>()

  init {
    for(i in 0 until 9){
      val rnd = Random()
      listToSort.add(ListUiItem(
        id = i,
        isCurrentlyCompared = false,
        value = rnd.nextInt(150),
        color = Color(
          255,
          rnd.nextInt(256),
          rnd.nextInt(256),
          255)
      )
      )
    }
  }

  fun startSorting(){
    viewModelScope.launch {
      bubbleSortUseCase(listToSort.map { listUiItem ->
        listUiItem.value
      }.toMutableList()).collect{ swapInfo ->
        val currentItemIndex = swapInfo.currentItem
        listToSort[currentItemIndex] = listToSort[currentItemIndex].copy(isCurrentlyCompared = true)
        listToSort[currentItemIndex+1] = listToSort[currentItemIndex+1].copy(isCurrentlyCompared = true)

        if(swapInfo.shouldSwap){
          val firstItem = listToSort[currentItemIndex].copy(isCurrentlyCompared = false)
          listToSort[currentItemIndex] = listToSort[currentItemIndex+1].copy(isCurrentlyCompared = false)
          listToSort[currentItemIndex+1] = firstItem
        }
        if(swapInfo.hadNoEffect){
          listToSort[currentItemIndex] = listToSort[currentItemIndex].copy(isCurrentlyCompared = false)
          listToSort[currentItemIndex+1] = listToSort[currentItemIndex+1].copy(isCurrentlyCompared = false)
        }
      }
    }
  }
}

1. SortViewModel sınıfı, Android Jetpack'in bir parçası olan ViewModel sınıfından türetilmiştir. Bu sınıf, uygulama verilerini koruyarak, kullanıcı arayüzü ile veri arasında bağlantı kurar ve veri işleme işlevlerini gerçekleştirir.
2. bubbleSortUseCase adında bir BubbleSortUseCase örneği, bu sınıfın özelliklerinden biridir. Bu örnek, sıralama algoritmasının gerçekleştirilmesinden sorumludur.
3. listToSort adında bir mutableStateListOf<ListUiItem> değişkeni, sıralanacak olan öğelerin listesini temsil eder. Bu liste, sıralama algoritması tarafından sıralanacak ve kullanıcı arayüzünde gösterilecektir. mutableStateListOf, Compose için özel bir liste türüdür ve veri değişikliklerini otomatik olarak izler ve günceller.
4. init bloğu, sınıf oluşturulduğunda çalışır ve listToSort listesine rastgele öğeler ekler. Her bir öğe, ListUiItem sınıfından oluşturulur ve rasgele bir değerle ve renkle birlikte listeye eklenir.
5. startSorting işlevi, sıralama işlemini başlatmak için kullanılır. Bu işlev, sıralama işleminin gerçekleştirilmesi için bubbleSortUseCase kullanarak bir akış oluşturur ve bu akışı toplar (collect). Her bir adımda, sıralama işleminin ilerlemesi listToSort listesindeki öğelerin durumunu güncelleyerek kullanıcı arayüzüne yansıtılır.

Bu şekilde, SortViewModel sınıfı, sıralama işleminin gerçekleştirilmesini ve kullanıcı arayüzünde gösterilmesini sağlar.

class MainActivity : ComponentActivity() {

  private val sortViewModel = SortViewModel()
  @OptIn(ExperimentalFoundationApi::class)
  override fun onCreate(savedInstanceState: Bundle?) {
    super.onCreate(savedInstanceState)
    setContent {
      BubbleSortTheme {
        window.statusBarColor = orange.toArgb()
        window.navigationBarColor = orange.toArgb()
        Column(
          modifier = Modifier
            .fillMaxSize()
            .background(gray)
            .padding(20.dp)
          ,
          horizontalAlignment = Alignment.CenterHorizontally,
          verticalArrangement = Arrangement.spacedBy(10.dp)
        ){
          Button(onClick = {
            sortViewModel.startSorting()
          }, colors = ButtonDefaults.buttonColors(containerColor = orange)
          ) {
            Text(
              "Sort List",
              fontWeight = FontWeight.Bold,
              fontSize = 22.sp
            )
          }
          LazyColumn(
            modifier = Modifier,
            verticalArrangement = Arrangement.spacedBy(15.dp)
          ){
            items(
              sortViewModel.listToSort,
              key = {
                it.id
              }
            ){
              val borderStroke = if(it.isCurrentlyCompared){
                BorderStroke(width = 3.dp,Color.White)
              }else{
                BorderStroke(width = 0.dp,Color.Transparent)
              }
              Box(
                modifier = Modifier
                  .size(60.dp)
                  .background(it.color, RoundedCornerShape(15.dp))
                  .border(borderStroke, RoundedCornerShape(15.dp))
                  .animateItemPlacement(
                    tween(300)
                  ),
                contentAlignment = Alignment.Center
              ){
                Text(
                  "${it.value}",
                  fontWeight = FontWeight.Bold,
                  fontSize = 22.sp
                )
              }
            }
          }
        }
      }
    }
  }
}

1. Kullanıcı arayüzü, bir düğme ve bir liste olarak oluşturulur. Düğme, sıralama işlemini başlatır. Liste, LazyColumn kullanılarak oluşturulur ve her bir öğe Box kullanılarak temsil edilir.
2. Liste öğeleri, sortViewModel.listToSort listesinden alınır ve Box içinde gösterilir. Her bir öğe, Text bileşeni kullanılarak değeri gösterilir.
3. Liste öğelerinin arka plan rengi ve kenarlık kalınlığı, isCurrentlyCompared özelliğine bağlı olarak değişir. Bu özellik, sıralama algoritmasının her bir adımında ilgili öğenin karşılaştırılma durumunu belirtir.

Bu şekilde, MainActivity sınıfı, sıralama algoritmasının çalıştırılmasını ve sonucunun kullanıcı arayüzünde gösterilmesini yönetir.

Bir başka Android ile ilgili yazımda görüşmek üzere, güzel günler dilerim. :)

Bütün kodlarını aşağıdaki github adresinde bulabilirsiniz.

https://github.com/Bahadireray/BubbleSortInJetpackCompose