# Tugas Pendahuluan 7 - Sorting
```txt
Nama : Hasan Abdullah Azzam
NPM : 2406428314
```
> 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)
- Bubble sort:
metode ini berkerja dengan cara membandingan pasangan elemen yang saling berdekatan dan mengaturnya sesuai posisi yang tepat, proses ini dilakukkan berulang kali hingga semua elemen data sudah tersusun.
time complexity = O(n^2)
cth `arr = {3,2,4,1,5}`
-> cek 3 dan 2 -> tukar -> `{2,3,4,1,5}`
-> cek 2 dan 4 -> sudah tepat -> `{2,3,4,1,5}`
-> cek 4 dan 1 -> tukar -> `{2,3,1,4,5}`
-> dan ulangi seterusnya.
- Selection sort:
Metode ini bekerja dengan memilih elemen terkecil dari array elemen dan mengaurnya keposisi pertama, proses ini di ulanggi untuk elemen sisanya hingga semua lemen sudah terurut.
time complexity = O(n^2)
cth `arr = {3,2,4,1,5}`
-> min dari `{3,2,4,1,5}` = `1`-> tukar dengan 3 -> `{1,2,4,3,5}`
-> min dari `{3,2,4,5}` = `2` -> sudah tepat -> `{1,2,4,3,5}`
-> ulangi hingga semua lemen sesuai.
perbedaan:
- jika bubble short mebanding kan setiap padanagn yang berdekatan dan menyebabkan banya penukaran posisi, sedangkkan selection short, hanya melakkukan pertukaran di setiap iterasi saja.
- logika bubble short lebih sederhana karena hanya perulangan sedangkan dalam selection short kita harus mencari nilai terkecil lebih dulu.
- namun, jumlah perbandingan slection short lebih sedkit karen asetiap iterasi jumlah nya an berkuarang, seddangkan bubble short lebih banyak.
#### Referensi
- GeeksforGeeks, “Bubble Sort Algorithm,” GeeksforGeeks, Feb. 02, 2014. https://www.geeksforgeeks.org/bubble-sort-algorithm/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 2025).
- GeeksforGeeks, “Selection Sort,” GeeksforGeeks, Jan. 31, 2014. https://www.geeksforgeeks.org/selection-sort-algorithm-2/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 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)
**Quick Short:**
metode ini bekerja dengan metode **divide and conquer** (metode membagi permaslahan menjadi lebih kecil agar lebih mudah menemukkan solusinya dan menggabuangkan solusinya diakhir), pengurutan dilakukkan dengan memilih elemen pivot dan mempartisinya, sehingga elemen yang lebih kecil berada di sisi kiri dan elemen yang lebih besar berada disisi kanan. proses ini di ulang untuk setiap partisinya hingga semua elemen berhasil terurut.
time complexity = O(nlogn)
**cth `arr = {3,2,4,1,5}`**
-> ambil pivot bebas-> elemen pertama `3`
-> partisis array-> bandingkan tiap elemen dengen pivot `3`
-> elemen lebih kecil taro dikiri sedangkan lebih besar dikanan
->{2,1} 3 {4,5}
-> rekursif fungsi quick short dengan elemen di tiap partisi->{2,1} dan {4,5}
-> terus ulangi hingga elemen partisi berjumlah 0/1
**Perbedaan dengan metode sebelum nya:**
- time complexity lebih singkat = nlogn
- membutugkan pivot
- lebih cepat dan efesien sehingga cocok untuk data yang besar
- namun, olgoritma yang digunakkan lebih komplex
- menggunakkan metode rekursif(divide and conquer) bukan iteratif.
#### Referensi
- GeeksforGeeks, “Quick Sort,” GeeksforGeeks, Jan. 07, 2014. https://www.geeksforgeeks.org/quick-sort-algorithm/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 2025).
- GeeksforGeeks, “Introduction to Divide and Conquer Algorithm,” GeeksforGeeks, Nov. 15, 2012. https://www.geeksforgeeks.org/introduction-to-divide-and-conquer-algorithm/ (accessed Apr. 14, 2025).
---
### 3. Jelaskan secara singkat algoritma sorting selain yang disebutkan pada pertanyaan sebelumnya! (10 poin)
- Insertion short:
metode yang menyisispkan tiap elemen di posisi yang benar.
dengan menggunakkan metode ini kita membagi array menjadi 2 partisi, yang sudah terurut dan yang teracak, selanjutnya kita mengecek setiap elemen di partisi teracak dan menempatkanya di tempat yang sesuai di partisi terurut, diawal kita mengangap elemen paling kiri sebagai pertisi terurut.
time complexty = O(n^2)
cth `arr = {3,2,4,1,5}`
->anggap `3` sudah sesuai-> uji 2 dengan 3-> tukar tempat `{2,3,4,1,5}`
-> uji 4 dengan 2 dan 3 -> sudah tepat > `{2,3,4,1,5}`
-> uji satu dengan 2,3,4-> update tempat-> `{1,2,3,4,5}`
- Merge short:
metode ini juga menggunakkan pendekatan divide and conquer, merge short akan membagi array menjadi 2 secara rekursif sehingga didapat sub bagian terkecil, selanutnya tiap sub bagian akan di shorting sesuai posisi nya dan digabungkan sehingga keseluruhan array akan terurut.
time complexity = O(nlogn)
cth `arr = {3,2,4,1,5}`
->bagi array->`{3,2,4}` dan` {1,5}`
-> `{3,2,4}` dan `{1,5}` ulanggi pembagian -> `{3,2}`,`{4}` dan `{1}`,`{5}`
->`{3,2}` bagi lagi->`{3},{2}`
-> gabungkan setelah shorting untuk `{3},{2}`->{2,3}
-> gabungkan dengan `{4}`->`{2,3,4}`
-> gabunggan partisi `{1}` dan `{5}`->`{1,5}`
->gabungkan `{2,3,4}` dan `{1,5`}->`{1,2,3,4,5}`
#### Referensi
- GeeksforGeeks, “Insertion Sort Algorithm,” GeeksforGeeks, Mar. 07, 2013. https://www.geeksforgeeks.org/insertion-sort-algorithm/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 2025).
- GeeksforGeeks, “Merge Sort Data Structure and Algorithms Tutorials,” GeeksforGeeks, Mar. 15, 2013. https://www.geeksforgeeks.org/merge-sort/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 2025).
---
### 4. Jelaskan cara mengurutkan array angka dalam urutan naik dan turun dalam C (12 poin)
untuk mengurutkan array angka kita bisa mengunakkan berbagai metode yag sudah di bahas sebelumnya,dan untuk membuat urutanya naik atau turun kita bisa mengaturnya di logika pengujianya.
contoh yang saya berikan menggunakkan etode insertion karena lebih efesien di array sedikit dan logika yang digunakkan cukup sederhana.
```c
#include<stdio.h>
//fungsi urutan naik
void insertionUp(int arr[], int n){
for(int i = 1; i < n; i++){
int curr = arr[i];
int j = i-1;
//perbedaanya di logika while
while(j>=0 && curr < arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
//fungsi urutan turun
void insertionDown(int arr[], int n){
for(int i = 1; i < n; i++){
int curr = arr[i];
int j = i-1;
//perbedaanya di logika while
while(j>=0 && curr > arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
void print(int arr[], int n){
for(int i = 0 ; i < n;i++){
printf("%d ",arr[i]);
}
printf("\n");
}
int main(){
int arr[]={5,2,4,3,1};
print(arr,5);
insertionUp(arr,5);
print(arr,5);
insertionDown(arr,5);
print(arr,5);
return 0;
}
```
#### Referensi
- GeeksforGeeks, “Insertion Sort Algorithm,” GeeksforGeeks, Mar. 07, 2013. https://www.geeksforgeeks.org/insertion-sort-algorithm/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 2025).
- Programiz, “Insertion Sort Algorithm,” Programiz.com, 2020. https://www.programiz.com/dsa/insertion-sort (accessed Apr. 14, 2025).
---
### 5. Jelaskan cara mengurutkan array struct berdasarkan field tertentu (bisa berupa integer atau string) (11 poin)
untuk megurutkan array struct berdasaran data didalamnya kita bisa menggunakkan cara yang mirirp pada soal sebelumnya, untuk angka kita bisa membandingkan tiap data di dalam struct nya sedangkan untuk string bisa menggunakkan nilai ascii nya atau kita tentukkan dulu nilai dari tiap string nya terlebih dahulu.
untuk membandingkan string menggunakkan nilai ASCII kita bisa menggunakkan fungsi `strcmp`.
selain ituada cara lain untuk mengurutkan string yaitu menentukanya tingkat string di awal terlebih dahulu.
cth:
string "one", "two", "three",dan "four', kumpulan string ini bisa kita ururtkan berdasarkan nilai angkanya dengan mengkonversinya sebagai angka terlebih dahulu, kita tidak bisa langusng membandingkanya karena urutanya tidak bergantung nilai ASCII
**perlu diingat pada saat menukar posisi urutan bukan hanya data yang ditukar tetapi keseluruhan struct**
```c
#include<stdio.h>
#include<string.h>
typedef struct{
char string[100];
int number;
}Object;
void insertionInt_Up(Object arr[], int n){
for(int i = 1; i < n; i++){
Object curr = arr[i];
int j = i-1;
while(j>=0 && curr.number < arr[j].number){
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
void insertionInt_Down(Object arr[], int n){
for(int i = 1; i < n; i++){
Object curr = arr[i];
int j = i-1;
while(j>=0 && curr.number > arr[j].number){
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
void insertionString_Up(Object arr[], int n){
for(int i = 1; i < n; i++){
Object curr = arr[i];
int j = i-1;
while(j>=0 && strcmp(curr.string,arr[j].string) < 0){
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
void insertionString_Down(Object arr[], int n){
for(int i = 1; i < n; i++){
Object curr = arr[i];
int j = i-1;
while(j>=0 && strcmp(curr.string,arr[j].string) > 0){
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = curr;
}
}
void print(Object arr[], int n){
for (int i = 0; i < n; i++) {
printf("%s, %d\n", arr[i].string, arr[i].number);
}
printf("\n");
}
int main(){
Object arr[5] = {
{"Jeruk", 20},
{"Apel", 15},
{"Mangga", 25},
{"Anggur", 10},
{"Pisang", 30}
};
print(arr,5);
printf("berdasarkan string naik\n\n");
insertionString_Up(arr,5);
print(arr,5);
printf("berdasarkan string turun\n\n");
insertionString_Down(arr,5);
print(arr,5);
printf("berdasarkan integer naik\n\n");
insertionInt_Up(arr,5);
print(arr,5);
printf("berdasarkan integer turun\n\n");
insertionInt_Down(arr,5);
print(arr,5);
return 0;
}
```
#### Referensi
- “Code With C,” Code with C, Oct. 09, 2014. https://www.codewithc.com/sorting-strings-alphabetically-in-c/?amp=1 (accessed Apr. 14, 2025).
- GeeksforGeeks, “Insertion Sort Algorithm,” GeeksforGeeks, Mar. 07, 2013. https://www.geeksforgeeks.org/insertion-sort-algorithm/?utm_source=geeksforgeeks&utm_medium=gfgcontent_shm&utm_campaign=shm (accessed Apr. 14, 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:
```c
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:
```c
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
```c
#include<stdio.h>
#include<string.h>
typedef struct{
char string[100];
int number;
}Object;
void insertionString_Up(Object arr[], int n){
for(int i = 1; i < n; i++){
Object curr = arr[i];
int j = i-1;
int temp = strcmp(curr.string,arr[j].string);
while(j >= 0){
int cmp = strcmp(curr.string, arr[j].string);
// karena logika while lebih panjang, dipisah saja, menjadi if didlam while, beda dengan soal soal sebelumnya.
if(cmp < 0 || (cmp == 0 && curr.number > arr[j].number)){
arr[j + 1] = arr[j];
j--;
} else {
break;
}
}
arr[j+1] = curr;
}
}
void print(Object arr[], int n){
for (int i = 0; i < n; i++) {
printf("%s, %d\n", arr[i].string, arr[i].number);
}
printf("\n");
}
int main(){
Object arr[8] = {
{"Jeruk", 20},
{"Apel", 15},
{"Mangga", 25},
{"Apel", 10},
{"Pisang", 30},
{"Apel", 40},
{"Mangga", 5},
{"Pisang", 20}
};
print(arr,8);
printf("hasil pengurutan berdasarkan string naik dan angka turun\n\n");
insertionString_Up(arr,8);
print(arr,8);
return 0;
}
```
Sign in with Wallet
Connect another wallet