Quick sort algorithm versus Bubble sort algorithm

Bubble sort Vs Quick sort

Bago tayo pumunta sa main event alamin muna natin ang bawat isang algorithm una Bubble sort.

Isa sa pinaka basic na sorting algorithm ang bubble sort? It is used in practice and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n²) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive. 

Isa sa pinaka basic na idea about dito ay ginagamit ito sa pamamagitan ng pag kukumpara sa bawat laman ng array isa-isa at pag katapos nito ay uulitin nito ang unang step kung saan mag sisimula ulit cya sa umpisa hangang sa matapos nito ang sorting.

Code:

// Example Program in C++

  // to sort an array

  // using bubble sort

  #include<iostream.h>

  void main(void)

  {

   int temp, i, j;

   int ar[10];

   cout<<"enter elements of array:\n";

   for(i=0; i<10; i++)

     cin>>ar[i];

   // sorting is done here

   for(i=0;i<10;i++)

     for(j=0; j<(10-1); j++)

       if (ar[j]>ar[j+1])

         {

          temp=ar[j];

          ar[j]=ar[j+1];

          ar[j+1]=temp;

         }

   // till here

 

   for(i=0; i<10; i++)

     cout<<endl<<ar[i];

 

   cout<<endl;

  }

Try ninyong gumamit ng program nito at makikita mu sa pag sisimulate mu ng mga code na isa isa nitong ikinukumpara ang  laman ng bawat array hangang sa  ito ay matapos. The best case of bubble sort is the ascending order of the number dahil direct nitong nalalaman kung na sort a ang mga laman ng array ngunit lahat ay may kahinaan and descending order ng number ng array ay lubhang nakaka apekto sa pag sosort ng algorithm na ito kaya lubhang mabagal ang pag sort nito kaysa sa ibang sorting algorithm.

Kung panu to nanggyayari e2 ang mga larawan at example

Quick sort naman tayo

            Ang quick sort algorithm ay isa sa pinaka mabilis na algorithm. Quicksort is a relatively simple sorting algorithm using the divide-and-conquer recursive procedure. It is the quickest comparison-based sorting algorithm in practice with an average running time.

          Mas madalas gamitin ang quick sort kaysa sa bubble sort kasi mas efficient ang quick sort algorithm dahil sa massive sorting nito.

panu nga ba gumagana ang quick sort?

Quicksort, like mergesort, is a divide-and-conquer recursive algorithm. The basic divide-and-conquer process for sorting a subarray S[p..r] is summarized in the following three easy steps: 

Divide: Partition S[p..r] into two subarrays S[p..q-1] and S[q+1..r] such that each element of S[p..q-1] is less than or equal to S[q], which is, in turn, less than or equal to each element of S[q+1..r]. Compute the index q as part of this partitioning procedure 

Conquer: Sort the two subarrays S[p...q-1] and S[q+1..r] by recursive calls to quicksort. 

Combine: Since the subarrays are sorted in place, no work is needed to combing them: the entire array S is now sorted.

QUICKSORT(S, P, r)

1 If p < r

2        then q <- PARTITION(S, p, r)

3                QUICKSORT(S, p, q-1)

4                QUICKSORT(S, q+1, r)

note: to sort the whole array S, the initial parameters would be: QUICKSORT(S, 1, length[A]) 

PARTITION(S, p, r)

1 x <- S[r]

2 i <- p-1

3 for j <- p to r-1

4        do if S[j] <= x

5                then i <- i+1

6                         swap S[i] <-> S[j]

7 swap S[i+1] <-> S[r]

8 return i+1

Quicksort's running time depends on the result of the partitioning routine - whether it's balanced or unbalanced. This is determined by the pivot element used for partitioning. If the result of the partition is unbalanced, quicksort can run as slowly as insertion sort; if it's balanced, the algorithm runs asymptotically as fast as merge sort. That is why picking the "best" pivot is a crucial design decision. 

The Wrong Way: the popular way of choosing the pivot is to use the first element; this is acceptable only if the input is random, but if the input is presorted, or in the reverse order, then the first elements provides a bad, unbalanced, partition. All the elements go either into S[p...q-1] or S[q+1..r]. If the input is presorted and as the first element is chosen consistently throughout the recursive calls, quicksort has taken quadratic time to do nothing at all. 

The Safe Way: the safe way to choose a pivot is to simply pick one randomly; it is unlikely that a random pivot would consistently provide us with a bad partition throughout the course of the sort. 

Median-of-Three Way: best case partitioning would occur if PARTITION produces two subproblems of almost equal size - one of size [n/2] and the other of size [n/2]-1. In order to achieve this partition, the pivot would have to be the median of the entire input; unfortunately this is hard to calculate and would consume much of the time, slowing down the algorithm considerably. A decent estimate can be obtained by choosing three elements randomly and using the median of these three as the pivot.

code:

#include <stdio.h>

#include <stdlib.h>

void swap(int *x,int *y)

{

   int temp;

   temp = *x;

   *x = *y;

   *y = temp;

}

int choose_pivot(int i,int j )

{

   return((i+j) /2);

}

void quicksort(int list[],int m,int n)

{

   int key,i,j,k;

   if( m < n)

   {

      k = choose_pivot(m,n);

      swap(&list[m],&list[k]);

      key = list[m];

      i = m+1;

      j = n;

      while(i <= j)

      {

         while((i <= n) && (list[i] <= key))

                i++;

         while((j >= m) && (list[j] > key))

                j--;

         if( i < j)

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

      }

      // swap two elements

      swap(&list[m],&list[j]);

      // recursively sort the lesser list

      quicksort(list,m,j-1);

      quicksort(list,j+1,n);

   }

}

void printlist(int list[],int n)

{

   int i;

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

      printf("%d\t",list[i]);

}

void main()

{

   const int MAX_ELEMENTS = 10;

   int list[MAX_ELEMENTS];

   int i = 0;

    

   // generate random numbers and fill them to the list

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

       list[i] = rand();

   }

   printf("The list before sorting is:\n");

   printlist(list,MAX_ELEMENTS);

    

   // sort the list using quicksort

   quicksort(list,0,MAX_ELEMENTS-1);

   // print the result

   printf("The list after sorting using quicksort algorithm:\n");

   printlist(list,MAX_ELEMENTS);

}

And the Result iS!!!

Quick Sort Algorithm Wins!!!!

- quick sort is better than the bubble sort because of possibility na ang set ng array ay kadalasan ay hindi na ka sort agad kaya ang 

suggestion ko ay mas magandang gamitin ang quick sort.

-Adrian Paul Q. Liveta

-200910042

Reference:

http://www.algolist.net/Algorithms/Sorting/Bubble_sort

http://learning-computer-programming.blogspot.com/2007/06/sorting-array-using-bubble-sort.html

http://www.devx.com/vb2themax/Tip/18972

http://warp.povusers.org/grrr/bubblesort_eng.html

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/quickSort.htm

http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html

http://www.devx.com/vb2themax/Article/19900

http://warp.povusers.org/SortComparison/

http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html