# Tugas Pendahuluan 7 - Sorting

Nama  : Radithya Fawwaz Syahdi
NPM   : 2306203066

> Catatan: Soal Programming tidak perlu mencantumkan referensi, hanya soal Teori saja yang memerlukan referensi minimal 2.

## Teori

### 1. Pilih dua dari algoritma sorting berikut: Bubble Sort, Selection Sort, Insertion Sort, dan jelaskan cara kerjanya! Juga, jelaskan perbedaan di antara mereka! (15 poin)

---

#### 1. Bubble Sort
##### A. Definisi
Bubble sort adalah algoritma sorting yang membandingkan dua elemen di dalam sekumpulan data yang berdekatan dan menukarnya hingga berada dalam urutan yang diinginkan, biasanya dari yang terkecil sampai dengan yang terbesar atau sebaliknya. Sama seperti pergerakan gelembung udara di air yang naik ke permukaan, setiap elemen bergerak ke salah satu ujung di dalam list, array, dan tipe sekumpulan data sejenis pada setiap iterasi. Oleh karena itu, algoritma ini disebut bubble sort.

##### B. Cara Kerja
Misalkan terdapat proses sorting elemen array dalam urutan menaik.

###### i. Iterasi Pertama (Bandingkan dan Tukar)


1. Dimulai dari indeks pertama, bandingkan elemen pertama dan kedua.
2. Jika elemen pertama lebih besar dari elemen kedua, keduanya akan ditukar.
3. Sekarang, bandingkan elemen kedua dan ketiga. Tukar jika tidak berurutan.
4. Proses di atas berlanjut hingga elemen terakhir.

###### ii. Iterasi yang tersisa


Proses yang sama berlanjut untuk iterasi yang tersisa. Setelah setiap iterasi, elemen terbesar di antara elemen yang tidak diurutkan ditempatkan di akhir. Dalam tiap iterasi, perbandingan dilakukan hingga elemen terakhir yang belum diurutkan. Susunan diurutkan ketika semua elemen yang belum diurutkan telah ditempatkan pada posisi yang benar.

#### 2. Insertion Sort
##### A. Definisi
Insertion sort adalah algoritma sorting yang menempatkan elemen yang belum diurutkan pada tempat yang sesuai di setiap iterasi. Mekanisme insertion sort mirip dengan proses mengurutkan kartu di tangan dalam permainan kartu. Diasumsikan bahwa kartu pertama sudah diurutkan, lalu dipilih dan diambil kartu yang belum diurutkan. Jika kartu yang belum diurutkan lebih besar dari kartu di tangan, kartu tersebut ditempatkan di sebelah kanan. Jika tidak lebih besar, maka ditempatkan di sebelah kiri kartu yang di tangan. Dengan cara yang sama, kartu lain yang belum diurutkan diambil dan ditempatkan di tempat yang tepat. Pendekatan serupa digunakan oleh tipe insertion sort yang mengurutkan sekumpulan data dari yang terkecil sampai yang terbesar.

##### B. Cara Kerja


Misalkan kita perlu mengurutkan array tersebut dalam urutan menaik.


1. Elemen pertama dalam array diasumsikan telah diurutkan. Ambil elemen kedua dan simpan secara terpisah di key. Bandingkan key dengan elemen pertama. Jika elemen pertama lebih besar dari key, maka key ditempatkan di depan elemen pertama.


2. Sekarang, dua elemen pertama diurutkan. Ambil elemen ketiga dan bandingkan dengan elemen di sebelah kirinya. Letakkan tepat di belakang elemen yang lebih kecil darinya. Jika tidak ada elemen yang lebih kecil darinya, maka letakkan di awal array.


3. Lanjutkan untuk menempatkan setiap elemen yang belum diurutkan pada posisi yang benar di dalam array.


#### 3. Perbedaan Antara Bubble dan Insertion Sort

##### A. Insertion Sort
1. Teknik penyortiran mudah yang menyusun sekumpulan data akhir yang diurutkan dengan memindahkan satu elemen pada satu waktu.
2. Dalam insertion sort, satu elemen ditransfer pada satu waktu untuk membangun sekumpulan data yang diurutkan.
3. Jumlah swap yang lebih sedikit.
4. Lebih cepat jika dibandingkan dengan bubble sort.

##### B. Bubble Sort
1. Algoritma pengurutan berbasis perbandingan di mana elemen-elemen yang berdekatan harus dibandingkan dan perlu pertukaran elemen-elemen jika terdapat urutan yang salah dalam sekumpulan data tersebut.
2. Dalam algoritma bubble sort, elemen tetangga diperiksa dan akan terjadi pertukaran jika diperlukan atau terdapat urutan data yang salah.
3. Jumlah swap yang lebih banyak.
4. Lebih lambat jika dibandingkan dengan insertion sort.

#### Referensi

- Programiz, “Bubble Sort Algorithm,” Programiz.com, 2020. [Online]. Available: <https://www.programiz.com/dsa/bubble-sort>. [Diakses: 14-April-2025]
- Programiz, “Insertion Sort Algorithm,” Programiz.com, 2020. [Online]. Available: <https://www.programiz.com/dsa/insertion-sort>. [Diakses: 14-April-2025]
- “What is the Difference between Bubble Sort and Insertion Sort,” BYJUS. [Online]. Available: <https://byjus.com/gate/difference-between-bubble-sort-and-insertion-sort/>. [Diakses: 14-April-2025]

---

### 2. Pilih salah satu dari algoritma sorting berikut: Quick Sort, Merge Sort, dan jelaskan cara kerjanya! Juga, jelaskan perbedaan algoritma ini dengan algoritma sorting pada soal nomor 1! (12 poin)

---

#### A. Merge Sort
##### 1. Pengertian
Algoritma merge sort adalah algoritma divide-and-conquer yang mengurutkan array dengan terlebih dahulu memecahnya menjadi array yang lebih kecil, lalu menyusun kembali array tersebut dengan cara yang benar sehingga terurut. Pemecahan dan penyusunan array untuk mengurutkan array dilakukan secara rekursif.
###### i. Divide
Algoritma dimulai dengan memecah array menjadi bagian-bagian yang lebih kecil dan lebih kecil lagi hingga satu sub-array tersebut hanya terdiri dari satu elemen.
###### ii. Conquer
Algoritma menggabungkan kembali bagian-bagian kecil array dengan meletakkan nilai terendah terlebih dahulu, sehingga menghasilkan array yang terurut.

##### 2. Cara Kerja


1. Membagi array yang belum diurutkan menjadi dua sub-array, setengah dari ukuran aslinya.
2. Teruskan membagi sub-array selama bagian array saat ini memiliki lebih dari satu elemen.
3. Gabungkan dua sub-array dengan selalu meletakkan nilai terendah terlebih dahulu.
4. Terus gabungkan hingga tidak ada lagi sub-array yang tersisa.

#### B. Perbedaan Merge Sort dengan Sorting Algorithm pada Soal Pertama
1. Lebih kompleks untuk diterapkan karena memerlukan bagian kode tambahan untuk fungsi pembagian dan penggabungan array dalam proses divide-and-conquer.
2. Memakan lokasi memori tambahan karena terbentuk list baru setiap kali terjadi pembagian dan penggabungan array.
3. Perbandingan dilakukan antar subarray yang telah dibagi sebelum digabungkan lagi secara bertahap dan rekursif, sedangkan perbandingan elemen dalam algoritma di soal pertama dilakukan terhadap semua elemen array secara menyeluruh dan iteratif tanpa dibagi menjadi subarray.
4. Dalam worst case, lebih cepat untuk sorting dataset yang lebih besar karena kompleksitas waktunya yang logaritmik (n*logn) dibandingkan dengan algortima soal pertama yang kompleksitas waktunya bersifat kuadratik (n²).

#### Referensi

- W3Schools, “DSA Merge Sort,” www.w3schools.com. [Online]. Available: <https://www.w3schools.com/dsa/dsa_algo_mergesort.php>. [Diakses: 14-April-2025]
- Programiz, “Merge Sort Algorithm,” Programiz.com, 2019. [Online]. Available: <https://www.programiz.com/dsa/merge-sort>. [Diakses: 14-April-2025]
- “Ada Computer Science,” Ada Computer Science. [Online]. Available: <https://adacomputerscience.org/concepts/sort_sorting_compared>. [Diakses: 14-April-2025]

---

### 3. Jelaskan secara singkat algoritma sorting selain yang disebutkan pada pertanyaan sebelumnya! (10 poin)

---

#### 1. Counting Sort
##### A. Definisi
Counting sort adalah algoritma sorting eksternal yang mengasumsikan semua nilai input adalah bilangan bulat yang berada di antara rentang 0 dan n. Kemudian dilakukan perhitungan matematis pada nilai input ini untuk menempatkannya pada posisi yang benar dalam array output. Algoritma ini menggunakan counter untuk menghitung frekuensi kemunculan angka dan mengaturnya sesuai dengan itu. Misalkan, jika angka m muncul 5 kali dalam urutan input, nilai counter angka akan menjadi 5 dan diulang 5 kali dalam array output.

##### B. Cara Kerja
1. Temukan elemen maksimum (misalkan maks) dari array yang diberikan.


2. Inisialisasi array counter dengan panjang maks+1 dan semua elemen 0. Array ini digunakan untuk menyimpan hitungan elemen dalam array yang akan diurutkan.


3. Menyimpan hitungan setiap elemen pada indeksnya masing-masing dalam array counter. Misalnya, jika hitungan elemen 3 adalah 2, maka 2 disimpan di posisi ke-3 dari array hitungan. Jika elemen "5" tidak ada dalam array, maka 0 disimpan di posisi ke-5.


4. Menyimpan jumlah kumulatif elemen dari array counter. Hal ini membantu dalam menempatkan elemen ke dalam indeks yang benar dari array yang diurutkan.


5. Temukan indeks setiap elemen dari array asli dalam array counter. Hal Ini akan memberikan jumlah kumulatif. Tempatkan elemen pada indeks yang dihitung seperti yang ditunjukkan pada gambar di bawah ini.


6. Setelah menempatkan setiap elemen pada posisi yang benar, kurangi jumlahnya sebanyak satu.

#### Referensi

- “Counting Sort Algorithm Overview,” Tutorialspoint.com, 2015. [Online]. Available: <https://www.tutorialspoint.com/data_structures_algorithms/counting_sort_algorithm.htm>. [Diakses: 14-April-2025]
- “Counting Sort (With Code),” www.programiz.com. [Online]. Available: <https://www.programiz.com/dsa/counting-sort>. [Diakses: 14-April-2025]
- “Counting Sort Algorithm Overview,” Tutorialspoint.com, 2015. [Online]. Available: <https://www.tutorialspoint.com/data_structures_algorithms/counting_sort_algorithm.htm>. [Diakses: 14-April-2025]

---

### 4. Jelaskan cara mengurutkan array angka dalam urutan naik dan turun dalam C (12 poin)

---

#### A. Pengurutan dengan Bubble Sort
Dapat digunakan sorting algorithm apa saja untuk mengurutkan array angka dalam urutan naik dan turun dalam C. Untuk contoh soal ini, akan digunakan algoritma bubble sort yang bekerja dengan membandingkan antaranggota array angka yang bersebelahan secara iteratif. Jika algoritma tersebut mengurutkan array angka secara naik, maka akan terjadi pertukaran antara dua elemen jika elemen di sebelah kiri lebih besar daripada elemen di sebelah kanan sehingga elemen dengan nilai besar relatif terhadap elemen lain akan menggelembung atau tergeser ke sebelah kanan array. Hal sebaliknya berlaku untuk pengurutan secara menurun, di mana akan terjadi pertukaran antara dua elemen jika elemen di sebelah kiri lebih kecil daripada elemen di sebelah kanan sehingga elemen dengan nilai kecil relatif terhadap elemen lain akan menggelembung atau tergeser ke sebelah kanan array. Untuk algoritma ringkas bubble sort :

##### 1. Iterasi Pertama (Bandingkan dan Tukar)
1. Dimulai dari indeks pertama, bandingkan elemen pertama dan kedua.
2. Dalam mode pengurutan secara naik, jika elemen pertama lebih besar dari elemen kedua, keduanya akan ditukar.
3. Dalam mode pengurutan secara turun, jika elemen pertama lebih kecil dari elemen kedua, keduanya akan ditukar.
4. Sekarang, bandingkan elemen kedua dan ketiga. Tukar jika tidak berurutan sesuai mode pengurutan.
5. Proses di atas akan terus berlanjut hingga elemen terakhir.

##### 2. Iterasi Kedua
Proses yang sama berlanjut untuk iterasi yang tersisa. Setelah setiap iterasi, elemen terbesar atau terkecil di antara elemen yang tidak diurutkan ditempatkan di akhir sesuai mode pengurutan. Dalam tiap iterasi, perbandingan dilakukan hingga elemen terakhir yang belum diurutkan. Susunan diurutkan ketika semua elemen yang belum diurutkan telah ditempatkan pada posisi yang benar.

Contoh bubble sort untuk mengurutkan array angka adalah sebagai berikut :

#include <stdio.h>

void printarr(int array[], int size) {
	for (int i = 0; i < size; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");
}

void bubbleSort(int array[], int size, int key) {
  for (int step = 0; step < size - 1; ++step) {
    for (int i = 0; i < size - step - 1; ++i) {
      if (array[i] > array[i + 1] && key) {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
      if (array[i] < array[i + 1] && !key) {
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

int main () {
	int arr[] = {4, 7, 2, 5, 9}, key;
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("Unsorted Array : ");
	printarr(arr, size);
	printf("Choose '0' for descending order and '1' ascending order.\n");
	scanf("%d", &key);
	while (key != 0 && key != 1) {
		printf("Please try again.\n");
		scanf("%d", &key);
	}
	bubbleSort(arr, size, key);
	printf("Sorted Array : ");
	printarr(arr, size);
	return 0;
}

#### Referensi

- Programiz, “Bubble Sort Algorithm,” Programiz.com, 2020. [Online]. Available: <https://www.programiz.com/dsa/bubble-sort>. [Diakses: 14-April-2025]
- w3schools, “DSA Bubble Sort,” www.w3schools.com. [Online]. Available: <https://www.w3schools.com/dsa/dsa_algo_bubblesort.php>. [Diakses: 14-April-2025]
- “C Program for Bubble Sort (4 Ways With Code),” WsCube Tech, 2025. [Online]. Available: <https://www.wscubetech.com/resources/c-programming/programs/bubble-sort>. Diakses: 14-April-2025]

---

### 5. Jelaskan cara mengurutkan array struct berdasarkan field tertentu (bisa berupa integer atau string) (11 poin)

---

#### A. Pengurutan dengan Bubble Sort
Untuk mengurutkan array struktur berdasarkan tipe anggota tertentu, dapat digunakan algoritma sorting seperti yang digunakan dalam soal keempat. Penulisannya mirip dan terdapat modifikasi kecil agar dapat mengakomodasi array struktur, contohnya arr[] diganti menjadi numb[].value1. Dalam pemecahan masalah sortir kali ini, akan digunakan algoritma bubble sort. Seperti sebelumnya, anggota dapat disortir dalam urutan naik maupun turun dan proses pengurutan hanya dapat dilakukan untuk anggota dengan tipe data yang sama pada satu waktu saja sehingga pengurutan untuk tipe data berbeda harus dilakukan secara terpisah atau loop yang berbeda. Secara umum untuk bubble sort, pengurutan lebih baik dilakukan untuk satu anggota pada satu waktu saja sebelum berpindah ke anggota berikutnya dan tidak secara sekaligus untuk mempermudah implementasi

Cara kerja bubble sort untuk pengurutan integer kali ini mirip dengan cara kerja yang dijelaskan di soal keempat, hanya saja anggota array di dalam kode diganti dengan anggota integer dari array struktur. Prinsip tersebut juga tidak terlalu jauh untuk penyortiran double, float, san char. Khusus untuk pengurutan string, baik sebagai anggota struktur ataupun tidak, diperlukan algoritma tambahan dalam mengolah string yang pada dasarnya berupa char array. Proses pengurutan string dapat dipermudah dengan memanfaatkan fungsi di dalam modul string.h, seperti strcmp() untuk membandingkan nilai antarstring dan strcpy() untuk menyalin string maupun menukar string antarvariabel. String juga dapat disortir secara kostum dengan variabel tambahan dan logika tambahan untuk menetapkan nilai tertentu ke string arbitrer, contohnya seperti "apel" = 1, "stroberi" = 3, dan lain-lainnya, ataupun langsung saja dengan membuat logika program yang memanfaatkan strcmp dan nilai yang dihasilkan dari perbandingannya. Contohnya adalah sebagai berikut :

#include <stdio.h>
#include <string.h>

typedef struct {
	char animalName[100];
	int animalNumb;
} Animal;

void priorityAnimal(Animal cuties[], int size, int helper[]) {
	for (int i = 0; i < size; i++) {
		if (strcmp(cuties[i].animalName, "owl") == 0) {
			helper[i] = 1;
		} else if (strcmp(cuties[i].animalName, "snake") == 0) {
			helper[i] = 2;
		} else if (strcmp(cuties[i].animalName, "elephant") == 0) {
			helper[i] = 3;
		} else if (strcmp(cuties[i].animalName, "cat") == 0) {
			helper[i] = 4;
		}
	}
}

void bubbleSort(Animal cuties[], int size) {
	char tempc[100];
	int helper[size], tempi;
	priorityAnimal(cuties, size, helper);
	for (int step = 0; step < size - 1; ++step) {
	    for (int i = 0; i < size - step - 1; ++i) {
	    	if (helper[i] > helper[i + 1]) {
	        	strcpy(tempc, cuties[i].animalName);
	        	strcpy(cuties[i].animalName, cuties[i + 1].animalName);
	        	strcpy(cuties[i + 1].animalName, tempc);
	    	}
		}
	}
	for (int step = 0; step < size - 1; ++step) {
	    for (int i = 0; i < size - step - 1; ++i) {
	    	if (cuties[i].animalNumb < cuties[i + 1].animalNumb && 
				strcmp(cuties[i].animalName, cuties[i + 1].animalName) == 0) {
				tempi = cuties[i].animalNumb;	
		        cuties[i].animalNumb = cuties[i + 1].animalNumb;
		        cuties[i + 1].animalNumb = tempi;
	      	}
	    }
	}
}

void printStruct(Animal cuties[], int size) {
	for (int i = 0; i < size; ++i) {
	    printf("%s %d\n", cuties[i].animalName, cuties[i].animalNumb);
	}
	printf("\n");
}

int main() {
	Animal cuties[] = {
		{"owl", 4},
		{"snake", 3},
	    {"owl", 2},
	    {"elephant", 1},
	    {"snake", 5},
	    {"elephant", 6},
	    {"cat", 1}
	};
	int size = sizeof(cuties) / sizeof(cuties[0]);
	printf("Unsorted Array of Structs :\n");
	printStruct(cuties, size);
	bubbleSort(cuties, size);
	printf("Sorted Array of Structs :\n");
	printStruct(cuties, size);
	return 0;
}

#### Referensi

- www.naukri.com, “Code 360 by Coding Ninjas,” Naukri.com, 2025. [Online]. Available: <https://www.naukri.com/code360/library/structure-sorting-in-c>. [Diakses: 14-April-2025]
- “C - Write program to Sort structure array using bubble sort,” Java2s.com, 2016. [Online]. Available: <http://www.java2s.com/example/c-book/write-program-to-sort-structure-array-using-bubble-sort.html>. [Diakses: 14-April-2025]
- GeeksforGeeks, “How to Sort an Array of Structs Based on a Member in C?,” GeeksforGeeks, Feb. 18, 2024. [Online]. Available: <https://www.geeksforgeeks.org/sort-array-of-structs-based-on-a-member-in-c/>. [Diakses: 14-April-2025]

---

## Pemrograman (40 poin)

> Masukkan screenshot layar output kode Anda di tempat yang disediakan.

### Mengurutkan Struct dengan Urutan String Custom

Sebuah objek berisi string dan integer. Anda perlu mengurutkan objek berdasarkan string dalam urutan naik. Jika string sama, maka urutkan berdasarkan integer dalam urutan turun.

Sebagai contoh, array objek adalah:

struct Object {
    char string[100];
    int number;
};

---

struct Object objects[] = {
    {"one", 4},
    {"two", 3},
    {"one", 2},
    {"three", 1},
    {"two", 5},
    {"three", 6}
    {"four", 1}
};

> Jika kita mengurutkan string secara alfabetis, kita mendapatkan: `four, one, three, two`. Kita ingin mengurutkan string `one, two, three, four`, jadi kode Anda perlu mengurutkan objek berdasarkan urutan string custom.

Output yang diharapkan adalah:

one 4
one 2
two 5
two 3
three 6
three 1
four 1

> **Catatan:** ubah `object` ke nama lain yang menurut Anda lebih sesuai, juga ubah string dan integer ke nama yang tepat, dan ubah urutan string custom agar sesuai dengan kasus spesifik Anda.
> Sebagai contoh `one, two, three, four` dapat diubah menjadi `apple, banana, cherry, date` dan Objects dapat diubah menjadi `Fruits`, dll. Jangan lupa untuk mengubah nama struct dan nama variabel.

---

### Jawaban Anda

#include <stdio.h>
#include <string.h>

typedef struct {
	char numbstr[100];
	int numbint;
} MathOrder;

void priorityOrder(MathOrder number[], int size, int helper[]) {
	for (int i = 0; i < size; i++) {
		if (strcmp(number[i].numbstr, "one") == 0) {
			helper[i] = 1;
		} else if (strcmp(number[i].numbstr, "two") == 0) {
			helper[i] = 2;
		} else if (strcmp(number[i].numbstr, "three") == 0) {
			helper[i] = 3;
		} else if (strcmp(number[i].numbstr, "four") == 0) {
			helper[i] = 4;
		}
	}
}

void bubbleSort(MathOrder number[], int size) {
	char tempc[100];
	int helper[size], tempi;
	priorityOrder(number, size, helper);
	for (int step = 0; step < size - 1; ++step) {
	    for (int i = 0; i < size - step - 1; ++i) {
	    	if (helper[i] > helper[i + 1]) {
	        	strcpy(tempc, number[i].numbstr);
	        	strcpy(number[i].numbstr, number[i + 1].numbstr);
	        	strcpy(number[i + 1].numbstr, tempc);
	    	}
		}
	}
	for (int step = 0; step < size - 1; ++step) {
	    for (int i = 0; i < size - step - 1; ++i) {
	    	if (number[i].numbint < number[i + 1].numbint && 
				strcmp(number[i].numbstr, number[i + 1].numbstr) == 0) {
				tempi = number[i].numbint;	
		        number[i].numbint = number[i + 1].numbint;
		        number[i + 1].numbint = tempi;
	      	}
	    }
	}
}

void printStruct(MathOrder number[], int size) {
	for (int i = 0; i < size; ++i) {
	    printf("%s %d\n", number[i].numbstr, number[i].numbint);
	}
	printf("\n");
}

int main() {
	MathOrder number[] = {
		{"one", 4},
		{"two", 3},
	    {"one", 2},
	    {"three", 1},
	    {"two", 5},
	    {"three", 6},
	    {"four", 1}
	};
	int size = sizeof(number) / sizeof(number[0]);
	printf("Unsorted Array of Structs :\n");
	printStruct(number, size);
	bubbleSort(number, size);
	printf("Sorted Array of Structs :\n");
	printStruct(number, size);
	return 0;
}