Praktikum 6 dan Praktikum 7 (Coding Bahasa C: Algoritma pengurutan dan algoritma pencarian)

 

Praktikum 6 (Algoritma Pengurutan)

A. Persoalan

1. Bubble Sort:

Buatlah program dalam bahasa C yang menggunakan algoritma Bubble Sort untuk
mengurutkan array berikut secara menaik: {9, 5, 2, 7, 1}.
Tampilkan hasil pengurutan array setelah proses Bubble Sort.

2. Selection Sort:

Buatlah program dalam bahasa C yang menggunakan algoritma Selection Sort untuk
mengurutkan array berikut secara menurun: {3, 8, 1, 6, 4}.
Tampilkan hasil pengurutan array setelah proses Selection Sort.

3. Insertion Sort:

Buatlah program dalam bahasa C yang menggunakan algoritma Insertion Sort untuk
mengurutkan array berikut secara menaik: {12, 6, 9, 3, 2}.
Tampilkan hasil pengurutan array setelah proses Insertion Sort.

4. Merge Sort:

Buatlah program dalam bahasa C yang menggunakan algoritma Merge Sort untuk
mengurutkan array berikut secara menurun: {10, 4, 7, 2, 9}.
Tampilkan hasil pengurutan array setelah proses Merge Sort.

5. Quick Sort:

Buatlah program dalam bahasa C yang menggunakan algoritma Quick Sort untuk mengurutkan
array berikut secara menaik: {5, 1, 8, 3, 6}.
Tampilkan hasil pengurutan array setelah proses Quick Sort.

B. Penyelesaian

1. Bubble Sort:

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  void bubbleSort(int arr[], int n) {

      for (int i = 0; i < n - 1; i++) {

          for (int j = 0; j < n - i - 1; j++) {

              if (arr[j] > arr[j + 1]) {

                  int temp = arr[j];

                  arr[j] = arr[j + 1];

                  arr[j + 1] = temp;

              }

          }

      }

  }

  
  

  int main() {

      int arr[] = {9, 5, 2, 7, 1};

      int n = sizeof(arr) / sizeof(arr[0]);

  
  

      bubbleSort(arr, n);

  
  

      printf("Hasil pengurutan dengan Bubble Sort:\n");

      for (int i = 0; i < n; i++) {

          printf("%d ", arr[i]);

      }

      printf("\n");

  
  

      return 0;

  }
• Hasil
  
  

2. Selection Sort

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  void selectionSort(int arr[], int n) {

      for (int i = 0; i < n - 1; i++) {

          int minIndex = i;

          for (int j = i + 1; j < n; j++) {

              if (arr[j] > arr[minIndex]) {

                  minIndex = j;

              }

          }

          int temp = arr[i];

          arr[i] =arr[minIndex];

          arr[minIndex] = temp;

      }

  }

  
  

  int main() {

      int arr[] = {3, 8, 1, 6, 4};

      int n = sizeof(arr) / sizeof(arr[0]);

  
  

      selectionSort(arr, n);

  
  

      printf("Hasil pengurutan dengan Selection Sort:\n");

      for (int i = 0; i < n; i++) {

          printf("%d ", arr[i]);

      }

      printf("\n");

  
  

      return 0;

  }
• Hasil
  
  

3. Insertion Sort

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  void insertionSort(int arr[], int n) {

      for (int i = 1; i < n; i++) {

          int key = arr[i];

          int j = i - 1;

          while ( j >= 0 && arr[j] > key) {

              arr[j + 1] = arr[j];

              j--;

          }

          arr[j + 1] = key;

      }

  }

  
  

  int main() {

      int arr[] = {12, 6, 9, 3, 2};

      int n = sizeof(arr) / sizeof(arr[0]);

  
  

      insertionSort(arr, n);

  
  

      printf("Hasil pengurutan dengan Insertion Sort:\n");

      for (int i = 0; i < n; i++) {

          printf("%d ", arr[i]);

      }

      printf("\n");

  
  

      return 0;

  }
• Hasil
  
  

4. Merge Sort

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  void merge(int arr[], int left, int mid, int right) {

      int i, j, k;

      int n1 = mid - left + 1;

      int n2 = right - mid;

      int L[n1], R[n2];

  
  

      for (i = 0; i < n1; i++) {

          L[i] = arr[left + i];

      }

      for (j = 0; j < n2; j++) {

          R[j] = arr[mid + 1 + j];

      }

  
  

      i = 0;

      j = 0;

      k = left;

  
  

      while (i < n1 && j < n2) {

          if (L[i] >= R[j]) {

              arr[k] = L[i];

              i++;

          } else {

              arr[k] = R[j];

              j++;

          }

          k++;

      }

  
  

      while (i < n1) {

          arr[k] = L[i];

          i++;

          k++;

      }

  
  

      while (j < n2) {

          arr[k] = R[j];

          j++;

          k++;

      }

  }

  
  

  void mergeSort(int arr[], int left, int right) {

      if (left < right) {

          int mid = left + (right - left) / 2;

          mergeSort(arr, left, mid);

          mergeSort(arr, mid + 1, right);

          merge(arr, left, mid, right);

      }

  }

  
  

  int main() {

      int arr[] = {10, 4, 7, 2, 9};

      int n = sizeof(arr) / sizeof(arr[0]);

  
  

      mergeSort(arr, 0, n-1);

  
  

      printf("Hasil pengurutan dengan Merge Sort:\n");

      for (int i = 0; i < n; i++) {

          printf("%d ", arr[i]);

      }

      printf("\n");

  
  

      return 0;

  }
• Hasil
  
  

5. Quick Sort

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  void swap(int* a, int* b) {

      int temp = *a;

      *a = *b;

      *b = temp;

  }

  
  

  int partition(int arr[], int low, int high) {

      int pivot = arr[high];

      int i = (low - 1);

  
  

      for (int j = low; j <= high - 1; j++) {

          if (arr[j] < pivot) {

              i++;

              swap(&arr[i], &arr[j]);

          }

      }

      swap(&arr[i + 1], &arr[high]);

      return (i + 1);

  }

  
  

  void quickSort(int arr[], int low, int high) {

      if (low < high) {

          int pi = partition(arr, low, high);

          quickSort(arr, low, pi - 1);

          quickSort(arr, pi + 1, high);

      }

  }

  
  

  int main() {

      int arr[] = {5, 1, 8, 3, 6};

      int n = sizeof(arr) / sizeof(arr[0]);

  
  

      quickSort(arr, 0, n - 1);

  
  

      printf("Hasil pengurutan dengan Quick Sort:\n");

      for (int i = 0; i < n; i++) {

          printf("%d ", arr[i]);

      }

      printf("\n");

  
  

      return 0;

  }
• Hasil
  
  

 

 

Praktikum 7 (Algoritma Pencarian)

A. Persoalan

1. Linear Search

Tuliskan program dalam bahasa C untuk melakukan linear search pada array integer.
Berikan penjelasan singkat tentang bagaimana linear search bekerja.
Hitung jumlah perbandingan yang dilakukan dalam linear search jika elemen yang dicari tidak
ada dalam array.

2. Binary Search

Tuliskan program dalam bahasa C untuk melakukan binary search pada array integer yang
sudah terurut.
Jelaskan konsep pembagian interval dalam binary search.
Hitung jumlah perbandingan yang dilakukan dalam binary search jika array memiliki 100
elemen.

3. Interpolation Search

Tuliskan program dalam bahasa C untuk melakukan interpolation search pada array integer.
Jelaskan konsep penggunaan interpolasi linear dalam interpolation search.
Hitung jumlah perbandingan yang dilakukan dalam interpolation search jika array memiliki
1000 elemen.

4. Jump Search

Tuliskan program dalam bahasa C untuk melakukan jump search pada array integer yang sudah
terurut.
Jelaskan konsep penggunaan langkah lompatan dalam jump search.
Hitung jumlah perbandingan yang dilakukan dalam jump search jika array memiliki 10000
elemen.

B. Penyelesaian

1. Linear Search

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  int linearSearch(int arr[], int n, int key) {

      for (int i = 0; i < n; i++) {

          if (arr[i] == key) {

              return i;

          }

      }

      return -1;

  }

  
  

  int main() {

      int arr[] = {2, 5, 8, 12, 16};

      int n = sizeof(arr) / sizeof(arr[0]);

      int key = 8;

      int index = linearSearch(arr, n, key);

      if (index != -1) {

          printf("Elemen ditemukan pada indeks %d\n", index);

      } else {

          printf("Elemen tidak ditemukan\n");

      }

      return 0;

  }
• Hasil
  
  
  

2. Binary Search

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  int binarySearch(int arr[], int low, int high, int key) {

      while (low <= high) {

      int mid = low + (high - low) / 2;

      if (arr[mid] ==  key) {

          return mid;

      } else if (arr[mid] < key) {

          low = mid + 1;

      } else {

          high = mid - 1;

      }

  }

  return -1;

  }

  
  

  int main() {

      int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};

      int n = sizeof(arr) / sizeof(arr[0]);

      int key = 7;

      int index = binarySearch(arr, 0, n - 1, key);

      if (index != -1) {

          printf("Elemen ditemukan pada indeks %d\n", index);

      } else {

          printf("Elemen tidak ditemukan\n");

      }

      return 0;

  }
• Hasil
  
  
  

3. Interpolation Search

• Koding Bahasa C
  
  #include <stdio.h>

  
  

  int interpolationSearch(int arr[], int n, int key) {

      int low = 0;

      int high = n - 1;

      while (low <= high && key >= arr[low] && key <= arr[high]) {

          int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);

          if (arr[pos] == key) {

              return pos;

          } else if (arr[pos] < key) {

              low = pos + 1;

          } else {

              high = pos - 1;

          }

      }

      return -1;

  }

  
  

  int main() {

      int arr[] = {3, 5, 9, 12, 15};

      int n = sizeof(arr) / sizeof(arr[0]);

      int key = 9;

      int index = interpolationSearch(arr, n, key);

      if (index != -1) {

          printf("Elemen ditemukan pada indeks %d\n", index);

      } else {

          printf("Elemen tidak ditemukan\n");

      }

      return 0;

  }
• Hasil
  
  
  

4. Jump Search

• Koding Bahasa C
  
  #include <stdio.h>

  #include <math.h>

  
  

  int jumpSearch(int arr[], int n, int key) {

      int step = sqrt(n);

      int prev = 0;

      while (arr[(int)fmin(step, n - 1)] < key) {

          prev = step;

          step += sqrt(n);

          if (prev >= n) {

              return -1; // Mengembalikan -1 jika elemen tidak ditemukan

          }

      }

      while (arr[prev] < key) {

          prev++;

          if (prev == (int)fmin(step, n)) {

              return -1; // Mengembalikan -1 jika elemen tidak ditemukan

          }

      }

      if (arr[prev] == key) {

          return prev; // Mengembalikan indeks elemen jika ditemukan

      }

      return -1; // Mengembalikan -1 jika elemen tidak ditemukan

  }

  
  

  int main() {

      int arr[] = {10, 20, 30, 40, 50};

      int n = sizeof(arr) / sizeof(arr[0]);

      int key = 20;

      int index = jumpSearch(arr, n, key);

      if (index != -1) {

          printf("Elemen ditemukan pada indeks %d\n", index);

      } else {

          printf("Elemen tidak ditemukan\n");

      }

      return 0;

  }
• Hasil