log.md

contoh list => 10, 7, 8, 9, 1, 5
arr = [10, 7, 8, 9, 1, 5]
for the line of code:

void quickSort(List<int> arr, int low, int high) {
  if (low >= high) return;
  int pi = partision(arr, low, high);

  quickSort(arr, low, pi - 1);
  quickSort(arr, pi + 1, high);
}

Flow dimulai dari line per line. Dimulai dari :

1. Kondisi antara low dan high (Jika kondisi low lebih besar dan sama dengan high)
2. Partision
3. quicSort sisi kiri pivot (range 0 - index sebelum pivot baru (setela partision))
4. quicSort sisi kanan pivot (range pivot baru - index terakhir)

1st Line : if (low >= high)

Note : Bagian ini untuk menghentikan quickSort karena bisa saja index pada pivot lebih kecil dari low
atau lebih besar dari high saat proses sorting setelah partising pertama. Hal ini bisa terjadi karena dalam proses sorting:

1. index pada pivot selalu berpindah ketika partising selesai
2. setelah partising pertama, list akan dibagi 2 antara index 0 sampai index sebelum pivot dan
   index setelah pivot sampai akhir length. Lalu setelah partising, kedua list akan melakukan hal yang sama
   (partising dan membagi list) dan akan berakhir sampai kondisi if (low >= high) tercapai

2nd Line : Partision

arr = [10, 7, 8, 9, 1, 5];
partision(arr, low, high) => partision(arr, 0, arr.length - 1)
=> parameter value:

1. arr = [10, 7, 8, 9, 1, 5]
2. low = 0;
3. high = length - 1 => high = (6) - 1 high = 5

int pivot = arr[high]; => int pivot = arr[5]; int pivot = 5;
int i = low - 1; => int i = (0) - 1; int i = -1; int j = low; => int j = 0

through while : (condition j <= high - 1 => j <= (5) - 1``j <= 4) (Range index(j) : 0 - 4)
while j = 0 :
if (arr[j] < pivot) => if (arr[0] < 5) if (10 < 5) (FALSE) :
no execution
j++ j = 0 => j = 1

while j = 1 :
if (arr[j] < pivot) => if (arr[1] < 5) if (7 < 5) (FALSE) :
no execution
j++ j = 1 => j = 2

while j = 2 :
if (arr[j] < pivot) => if (arr[2] < 5) if (8 < 5) (FALSE) :
no execution
j++ j = 2 => j = 3

while j = 3 :
if (arr[j] < pivot) => if (arr[3] < 5) if (9 < 5) (FALSE) :
no execution
j++ j = 3 => j = 4

while j = 4 :
if (arr[j] < pivot) => if (arr[4] < 5) if (1 < 5) (TRUE) :
>----execute :
i++; i = -1 => i = 0
Go to (function) swap (inside if):
partision : int swap(List<int> arr, int i, int j)
parameter current value:

1. i = i => i = 0
2. j = j => i = 4

int temp = arr[i]; => int temp = arr[0] int temp = 10
arr[i] = arr[j]; => arr[0] = arr[4] arr[0] = 1
arr[j] = temp; => arr[4] = temp arr[4] = 10
>----execute end | Status : now the current arr => [1, 7, 8, 9, 10, 5]
j++ j = 4 => j = 5
While End
Go to (function) swap (outside while):
partision : int swap(List<int> arr, int i, int j)
parameter current value:

1. i = i + 1 => i = (0) + 1 i = 1
2. j = high => j = 5

int temp = arr[i]; => int temp = arr[1] int temp = 7
arr[i] = arr[j]; => arr[1] = arr[5] arr[1] = 5
arr[j] = temp; => arr[5] = temp arr[5] = 7
now the current arr => [1, 5, 8, 9, 10, 7]

return i + 1; => return (0) + 1 return 1

3rd Line : quicSort sisi kiri pivot (range 0 - index sebelum pivot baru (setela partision))

quick_sort (3 main method).md

1. Melakukan swap / tukar nilai dari di dalam list

void swap(List<int> arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

2. Melakukan pencarian pivot

pencarian pivot baru untuk membagi list yang disorting menjadi 2 bagian. Caranya dengan melakukan looping terlebih
terlebih dahulu. Dimana dalam looping tersebut :

1. Sebelum looping menaruh indeks i = -1 dan j = 0 di awal,
2. Melakukan check kondisi jika nilai di index j lebih kecil dari pivot(index terbesar)
   maka i maju 1 dan nilai pada index i dan j akan di tukar.
3. j terus maju dan setelah itu mengulang kondisi di atas sampai
   j lebih kecil sama dengan index sebelum index terbesar dari array (high - 1)

Setelah loop selesai, maka i terakhir/ terkini maju 1 dan nilai pada index i yang maju ditukar dengan index terbesar. Pivot baru muncul dari partision, yaitu index i + 1.

int partision(List<int> arr, int low, int high) {
  int pivot = arr[high];
  
  int i = low - 1;
  int j = low;
  while (j <= high - 1) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
    j++;
  }
  swap(arr, i + 1, high);
  return i + 1;
}

3. eksekusi quick sort

Dari tahap eksekusi, quuck sort sendiri memiliki validasi jika nilao low lebih besar sama dengan dari high
maka qucksort berhenti. Validasi ini berfungsi ketika sudah masuk bagian recursivenya saja setelah melakukan
partising. 2 Recursive (memanggil quickSort) setelah partising akan melakukan sorting lagi, tapi seusai dengan bagiannya. Dimana :

1. quick sort pertama untuk : 0 s/d index sebelum partising baru
2. quick sort ke-2 untuk : index setelah partising baru s/d index terakhir

void quickSort(List<int> arr, int low, int high) {
  if (low >= high) return;
  int pi = partision(arr, low, high);

  quickSort(arr, low, pi - 1);
  quickSort(arr, pi + 1, high);
}

quick_sort.dart

void main() {
  final list = [10, 7, 8, 9, 1, 5 ];
  quickSort(list, 0, list.length - 1);
  print(list);
}

void swap(List<int> arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

int partision(List<int> arr, int low, int high) {
  int pivot = arr[high];
  
  int i = low - 1;
  int j = low;
  while (j <= high - 1) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
    j++;
  }
  swap(arr, i + 1, high);
  return i + 1;
}

void quickSort(List<int> arr, int low, int high) {
  if (low >= high) return;
  int pi = partision(arr, low, high);

  quickSort(arr, low, pi - 1);
  quickSort(arr, pi + 1, high);
}

simple_log.md

arr = [10, 7, 8, 9, 1, 5]

void quickSort(List<int> arr, int low, int high) {
  if (low >= high) return;
  int pi = partision(arr, low, high);

  quickSort(arr, low, pi - 1);
  quickSort(arr, pi + 1, high);
}

1. 1ft line if (low >= high) return; low >= hight => 0 >= 5 (FALSE) no execution

2. 2nd line int pi = partision(arr, low, high);

Show 2nd line step

Inisiasi dan deklarasi

pivot = arr[5] 5;
i = -1;
j = 0;

While j = 0

arr[0] < pivot; => 10 < 5 (FALSE) no execution j = 1

While j = 1

arr[1] < pivot; => 7 < 5 (FALSE) no execution j = 2

While j = 2

arr[2] < pivot; => 8 < 5 (FALSE) no execution j = 3

While j = 3

arr[3] < pivot; => 9 < 5 (FALSE) no execution j = 4

While j = 4

arr[4] < pivot; => 1 < 5 (TRUE)
i = 0
swap(arr, 0, 4) current arr = [1, 7, 8, 9, 10, 5]
j = 5

swap(arr, i + 1, high)

swap(arr, (0) + 1, 5)
current arr = [1, 5, 8, 9, 10, 7]

return i + 1; return (0) + 1 = 1;

3. 3rd line quickSort(arr, low, pi - 1); quickSort(arr, 0, (1) - 1)

3.1. 1ft line if (low >= high) return; low >= hight => 0 >= 0 (TRUE) return;

4. 4th line quickSort(arr, pi + 1, high); quickSort(arr, (1) + 1, 5)

Show 4th line step

4.1. 1ft line if (low >= high) return; low >= hight => 2 >= 5 (False)
no execution

4.2. 2nd line int pi = partision(arr, 2, 5);

Show 4.2. 2nd line step

Inisiasi dan deklarasi

pivot = arr[5] 7;
i = 1;
j = 2;

While j = 2

arr[2] < pivot; => 8 < 7 (FALSE) no execution j = 3

While j = 3

arr[3] < pivot; => 9 < 7 (FALSE) no execution j = 4

While j = 4

arr[4] < pivot; => 10 < 7 (FALSE) no execution j = 5

swap(arr, i + 1, high)

swap(arr, (1) + 1, 5) current arr = [1, 5, 7, 9, 10, 8]

return i + 1; return (1) + 1 = 2;

4.3. 3rd line quickSort(arr, low, pi - 1); quickSort(arr, 2, 1)

4.3.1. 1ft line if (low >= high) return; low >= hight => 2 >= 1 (TRUE) return;

4.4. 4th line quickSort(arr, low, pi - 1); quickSort(arr, 3, 5)

Show 4.4. 4th line step

4.4.1. 1ft line if (low >= high) return; low >= hight => 3 >= 5 (False)
no execution

4.4.2. 2nd line int pi = partision(arr, 3, 5);

Inisiasi dan deklarasi

pivot = arr[5] 8;
i = 2;
j = 3;

While j = 3

arr[3] < pivot; => 9 < 8 (FALSE) no execution j = 4

While j = 4

arr[4] < pivot; => 10 < 8 (FALSE) no execution j = 5

swap(arr, i + 1, high)

swap(arr, 9, 8) current arr = [1, 5, 7, 8, 10, 9]

return i + 1; return (2) + 1 = 3;

4.4.3. 3rd line quickSort(arr, low, pi - 1); quickSort(arr, 3, 2)

4.4.3.1 1ft line if (low >= high) return; low >= hight => 3 >= 2 (TRUE) return;

4.4.4. 4th line quickSort(arr, pi + 1, high); quickSort(arr, 4, 5)

4.4.4.1 1ft line if (low >= high) return; low >= hight => 4 >= 5 (FALSE)
no execution

4.4.4.2 2nd line int pi = partision(arr, low, high);

Inisiasi dan deklarasi

pivot = arr[5] 9;
i = 3;
j = 4;

While j = 4

arr[4] < pivot; => 10 < 9 (FALSE) no execution j = 5

swap(arr, i + 1, high)

swap(arr, 4, 5) current arr = [1, 5, 7, 8, 9, 10]