Home arrow JavaScript arrow QuickSort in Action
JAVASCRIPT

QuickSort in Action


This is the second part of a two-part article that explains how to use Quicksort. It is a method of sorting a list of elements and putting them in the correct order. Please make sure you have read and understood the first article before you read this one.

Author Info:
By: Chrysanthus Forcha
Rating: 4 stars4 stars4 stars4 stars4 stars / 4
October 27, 2008
TABLE OF CONTENTS:
  1. · QuickSort in Action
  2. · Swapping Elements
  3. · Tackling a Sub-list
  4. · And Then There was One
  5. · Code for Quicksort
  6. · Sorting Strings

print this article
SEARCH DEVARTICLES

TOOLS YOU CAN USE

advertisement
QuickSort in Action
(Page 1 of 6 )

Picking up where we left off in the previous article, we have to obtain a pivot and then put all elements that are less than the pivot on the left side and all elements that are greater than the pivot on the right side.

We start by comparing the left-most and right-most elements. If the left-most element is greater than the right-most element, then swap them. This gives the following:


Q

W

E

R

T

Y

U

I

O

P

i









j


P

W

E

R

T

Y

U

I

O

Q

i









j



For simplicity, we shall be calling the left-most element the left element, and the right-most element the right element.

The present left element will become the pivot for the list. We arrive here after the swapping phase. We then increase the value of i continuously until we come across an element that is greater than the left element. We reduce the value of j continuously until we come across an element that is less than the same left element; remember that the left element will become the pivot. The ith and the jth element so found are in the wrong positions, so we swap them. This gives rise to the following:


P

W

E

R

T

Y

U

I

O

Q


i







j



P

O

E

R

T

Y

U

I

W

Q


i







j



We continue to increase the value of i and decrease the value of j to find another pair of elements that are in the wrong positions, and then swap. This leads to:


P

W

E

R

T

Y

U

I

O

Q




i




j




P

O

E

I

T

Y

U

R

W

Q




i




j




We have to continue increasing the value of i, decreasing the value of j and swapping until the index variables reach the right (end) and left (start) elements. However, as soon as the index variables cross, it means we have finished swapping -- all the elements that should be on the left, and all the elements that should be on the right, are in their appropriate positions (or at least on their correct sides).


blog comments powered by Disqus
JAVASCRIPT ARTICLES

- More Top jQuery Plugins for Menus
- Top jQuery Tutorials for Beginners
- New UI Framework and SDK for JavaScript Rele...
- JavaScript OpenPGP Tool, Node.js 0.6.3 Avail...
- Yahoo Releases Cocktails Language and Develo...
- Customizing jQuery Slideshows: Dynamic Contr...
- Customizing jQuery Slideshows: the animate()...
- Customizing jQuery Slideshows: slideUp() and...
- Customizing jQuery Slideshows: hide() and sh...
- Web Workers: Performing Calculations in Para...
- More Top JavaScript Frameworks and Libraries
- More Dynamic jQuery Styling Techniques
- The Top JavaScript Libraries
- The Top JavaScript Frameworks
- Dynamic jQuery Styling

Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 



© 2003-2012 by Developer Shed. All rights reserved. DS Cluster 3 - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials