Menghitung Sortir di Jawa

1. Ikhtisar

Algoritme pengurutan untuk tujuan umum seperti Merge Sort tidak membuat asumsi tentang masukan, sehingga mereka tidak dapat mengalahkan O (n log n) dalam kasus terburuk. Counting Sort, sebaliknya, memiliki asumsi tentang input yang menjadikannya sebagai algoritma pengurutan waktu linier.

Dalam tutorial ini, kita akan berkenalan dengan mekanisme Counting Sort dan kemudian mengimplementasikannya di Java.

2. Menghitung Jenis

Counting sort, sebagai kebalikan dari kebanyakan algoritma pengurutan klasik, tidak mengurutkan input yang diberikan dengan membandingkan elemen. Sebaliknya, ini mengasumsikan bahwa elemen masukan adalah n bilangan bulat dalam rentang [0, k ] . Jika k = O (n), maka penghitungan akan berjalan dalam waktu O (n) .

Harap perhatikan, bahwa kami tidak dapat menggunakan jenis penghitungan sebagai algoritme pengurutan tujuan umum. Namun, ketika inputnya selaras dengan asumsi ini, itu cukup cepat!

2.1. Frekuensi Array

Misalkan kita akan mengurutkan larik inputdengan nilai dalam rentang [0, 5]:

Pertama, kita harus menghitung kemunculan setiap angka dalam larik input. Jika kita merepresentasikan hitungan dengan array C , maka C [i] merepresentasikan frekuensi angka i dalam array input :

Misalnya, karena 5 muncul 3 kali dalam larik input, nilai untuk indeks 5 sama dengan 3.

Sekarang diberikan array C, kita harus menentukan berapa banyak elemen yang kurang dari atau sama dengan setiap elemen masukan. Sebagai contoh:

  • Satu elemen kurang dari atau sama dengan nol, atau dengan kata lain hanya ada satu nilai nol yang sama dengan C [0]
  • Dua elemen kurang dari atau sama dengan satu, yang sama dengan C [0] + C [1]
  • Empat nilai kurang dari atau sama dengan dua, yaitu sama dengan C [0] + C [1] + C [2]

Jadi jika kita terus menghitung penjumlahan dari n elemen yang berurutan di C, kita bisa mengetahui berapa banyak elemen yang kurang dari atau sama dengan angka n-1 pada input array. Bagaimanapun, dengan menerapkan rumus sederhana ini kita dapat memperbarui C sebagai berikut:

2.2. Algoritma

Sekarang kita dapat menggunakan array tambahan C untuk mengurutkan array input. Berikut cara kerja jenis penghitungan:

  • Ini mengulang array input secara terbalik
  • Untuk setiap elemen i, C [i] - 1 mewakili lokasi bilangan i dalam larik yang diurutkan. Ini karena fakta bahwa ada unsur C [i] yang kurang dari atau sama dengan i
  • Kemudian, ia mengurangi C [i] di akhir setiap putaran

Untuk mengurutkan contoh larik masukan, pertama-tama kita harus mulai dengan angka 5, karena ini adalah elemen terakhir. Menurut C [5], ada 11 unsur yang kurang dari atau sama dengan bilangan 5.

Jadi, 5 harus menjadi elemen ke-11 dalam array yang diurutkan, maka indeks 10:

Karena kita pindah 5 ke array yang diurutkan, kita harus mengurangi C [5]. Elemen berikutnya dalam urutan terbalik adalah 2. Karena ada 4 elemen yang kurang dari atau sama dengan 2, nomor ini harus menjadi elemen ke-4 dalam larik yang diurutkan:

Demikian pula, kita dapat menemukan tempat yang tepat untuk elemen berikutnya yaitu 0:

Jika kita terus mengulang secara terbalik dan memindahkan setiap elemen dengan tepat, kita akan berakhir dengan sesuatu seperti:

3. Menghitung Jenis - Implementasi Java

3.1. Menghitung Array Frekuensi

Pertama, diberi larik input elemen dan k, kita harus menghitung larik C:

int[] countElements(int[] input, int k) { int[] c = new int[k + 1]; Arrays.fill(c, 0); for (int i : input) { c[i] += 1; } for (int i = 1; i < c.length; i++) { c[i] += c[i - 1]; } return c; }

Mari kita uraikan tanda tangan metode:

  • masukan mewakili larik angka yang akan kita urutkan
  • The masukan array array bilangan bulat di kisaran [0, k ] - sehingga k mewakili maksimum di masukan
  • Jenis yang dikembalikan adalah larik bilangan bulat yang mewakili larik C.

Dan inilah cara kerja metode countElements :

  • Pertama, kami menginisialisasi array C. Karena rentang [0, k] berisi angka k + 1 , kami membuat larik yang mampu berisi angka k + 1
  • Kemudian untuk setiap angka di input, kami menghitung frekuensi angka itu
  • Dan terakhir, kami menambahkan elemen yang berurutan untuk mengetahui berapa banyak elemen yang kurang dari atau sama dengan angka tertentu

Selain itu, kami dapat memverifikasi bahwa metode countElements berfungsi seperti yang diharapkan:

@Test void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() { int k = 5; int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 }; int[] c = CountingSort.countElements(input, k); int[] expected = { 1, 2, 4, 6, 8, 11 }; assertArrayEquals(expected, c); }

3.2. Menyortir Array Input

Sekarang kita bisa menghitung larik frekuensi, kita harus bisa mengurutkan set angka yang diberikan:

int[] sort(int[] input, int k) { int[] c = countElements(input, k); int[] sorted = new int[input.length]; for (int i = input.length - 1; i >= 0; i--) { int current = input[i]; sorted[c[current] - 1] = current; c[current] -= 1; } return sorted; }

Berikut cara kerja metode sortir :

  • Pertama, ini menghitung array C.
  • Then, it iterates the input array in reverse and for each element in the input, finds its correct spot in the sorted array. The ith element in the input should be the C[i]th element in the sorted array. Since Java arrays are zero-indexed, the C[i]-1 entry is the C[i]th element – for example, sorted[5] is the sixth element in the sorted array
  • Each time we find a match, it decrements the corresponding C[i] value

Similarly, we can verify that the sort method works as expected:

@Test void sort_GivenAnArray_ShouldSortTheInputAsExpected() { int k = 5; int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 }; int[] sorted = CountingSort.sort(input, k); // Our sorting algorithm and Java's should return the same result Arrays.sort(input); assertArrayEquals(input, sorted); }

4. Revisiting the Counting Sort Algorithm

4.1. Complexity Analysis

Most classic sorting algorithms, like merge sort, sort any given input by just comparing the input elements to each other. These type of sorting algorithms are known as comparison sorts. In the worst case, comparison sorts should take at least O(n log n) to sort n elements.

Counting Sort, on the other hand, does not sort the input by comparing the input elements, so it's clearly not a comparison sort algorithm.

Let's see how much time it consumes to sort the input:

  • It computes the C array in O(n+k) time: It once iterates an input array with size n in O(n) and then iterates the C in O(k) – so that would be O(n+k) in total
  • After computing the C, it sorts the input by iterating the input array and performing a few primitive operations in each iteration. So, the actual sort operation takes O(n)

In total, counting sort takes O(n+k) time to run:

O(n + k) + O(n) = O(2n + k) = O(n + k)

If we assume k=O(n), then counting sort algorithm sorts the input in linear time. As opposed to general-purpose sorting algorithms, counting sorts makes an assumption about the input and takes less than the O(n log n) lower bound to execute.

4.2. Stability

A few moments ago, we laid a few peculiar rules about the mechanics of counting sort but never cleared the reason behind them. To be more specific:

  • Why should we iterate the input array in reverse?
  • Why we decrement the C[i] each time we're using it?

Let's iterate from the beginning to better understand the first rule. Suppose we're going to sort a simple array of integers like the following:

In the first iteration, we should find the sorted location for the first 1:

So the first occurrence of number 1 gets the last index in the sorted array. Skipping the number 0, let's see what happens to the second occurrence of number 1:

The appearance order of elements with the same value is different in the input and sorted array, so the algorithm is not stable when we're iterating from the beginning.

What happens if we don't decrement the C[i] value after each use? Let's see:

Both occurrences of number 1 are getting the last place in the sorted array. So if we don't decrement the C[i] value after each use, we could potentially lose a few numbers while sorting them!

5. Conclusion

Dalam tutorial ini, pertama, kita mempelajari cara kerja Counting Sort secara internal. Kemudian kami menerapkan algoritme pengurutan ini di Java dan menulis beberapa tes untuk memverifikasi perilakunya. Dan terakhir, kami membuktikan bahwa algoritme tersebut merupakan algoritme pengurutan yang stabil dengan kompleksitas waktu linier.

Seperti biasa, kode sampel tersedia di proyek GitHub kami, jadi pastikan untuk memeriksanya!