quickSort Algorithm


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

Thread: quickSort Algorithm

Hybrid View

  1. #1
    john Guest

    quickSort Algorithm


    Can someone tell me where I can find how to impliment QuickSort Algorithm
    in Java. I just want to learn the technique and practice. I appreciate
    your help.

    john

  2. #2
    zave Guest

    Re: quickSort Algorithm


    "john" <john@cs.uwindsor.ca> wrote:
    >
    >Can someone tell me where I can find how to impliment QuickSort Algorithm
    >in Java. I just want to learn the technique and practice. I appreciate
    >your help.
    >
    >john



    1. If the number of elements in Sort is 0 or 1, them return.
    2. Pick any element in Sort. This element is called the pivot.
    3. Partition Sort-{element} (the remaining element is Sort) into two disjoint
    groups. L and R.
    4. Return the result of Quicksort(L), followed by Quicksort(R).

    part of the implementation would be....

    int middle = low+high)/2;
    if(a[middle].lessThen(a[low]))
    swapReferences( a, low, middle);
    if(a[high].lessThen(a[low]))
    swapReferences(a, low, highh);
    if(a[high].lessThen( a[middle]))
    swapRefrences( a, middle, high);

    for(int i = low, j=high-1; {
    whild(a[++i].lessThen(pivot));
    while(pivot.lessThen(a[--j]));
    if(i<j)
    swapReferences(a, j, i);
    else
    break;



    Well this is an algorithm and part of the implementation for quick sort.
    Hope this helps a little.




  3. #3
    Willy Van den Driessche Guest

    Re: quickSort Algorithm

    Have a look at the code at :
    http://users.skynet.be/wvdd2/Sorting/sorting.html
    The code is in VB, but you should have no problem converting it to Java.
    --
    Van den Driessche Willy
    For a work in progress :
    http://users.skynet.be/wvdd2/index.html



  4. #4
    Stellan Soderstrom Guest

    Re: quickSort Algorithm


    Hi,

    This is an implementation of Quicksort that sorts iteger arrays.
    The resulting, sorted list is stored in the same array as you pass
    as a parameter to the quickSort method.

    Good Luck,
    Stellan


    public static void quickSort(int[] list) {
    quickSort(list, 0, list.length - 1);
    }

    public static void quickSort(int[] list, int lo, int hi) {
    int pivot = lo;
    int h = lo;
    int tmp = 0;
    if(hi - lo <= 0) {
    return;
    }
    else if(hi - lo == 1) {
    if(list[lo] > list[hi]) {
    tmp = list[lo];
    list[lo] = list[hi];
    list[hi] = tmp;
    }
    return;
    }
    else {
    for(int i = lo + 1; i <= hi; i++) {
    if(list[i] > list[pivot] && pivot == h) {
    h++;
    }
    else if(list[i] <= list[pivot]) {
    // swich (p,h)
    tmp = list[pivot];
    list[pivot] = list[h];
    list[h] = tmp;
    // swich (p,i)
    tmp = list[pivot];
    list[pivot] = list[i];
    list[i] = tmp;

    pivot++;
    h++;
    }
    else {
    // nothing to do
    }
    }
    quickSort(list, lo, pivot - 1);
    quickSort(list, pivot + 1, hi);
    }
    }

    "john" <john@cs.uwindsor.ca> wrote:
    >
    >Can someone tell me where I can find how to impliment QuickSort Algorithm
    >in Java. I just want to learn the technique and practice. I appreciate
    >your help.
    >
    >john






Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center