Hello,all
I m just a newbie to c,and now i m learning quick sorting,i dont very
undertand this algorrithm,can someone kind to explain it to me?
the code:
<quote>
void quick_sort(int a[] ,int low ,int high)
{
int i =low;
int j =high ;
int t= a[i];
while(i<j)
{
while(i<j&&a[j]>t)
j--;
a[i] =a[j];
while(i<j&&a[i]<=t)
i++;
a[j] =a[i];
a[i] =t;
quick_sort(a,low,i-1);
quick_sort(a,i+1,high);
}
}
<quote>
why does the code do this, esp. after the second while-statement the
assignment"a[i]=a[j]",and the third while-statement the assignment
"a[j] =a[i]"?
I m very confused.Any reply is appreciated.Thanks.
-------------------------------pinkfog--------------------------------------------- 2 3623
pinkfog wrote: Hello,all I m just a newbie to c,and now i m learning quick sorting,i dont very undertand this algorrithm,can someone kind to explain it to me? the code: <quote> void quick_sort(int a[] ,int low ,int high) { int i =low; int j =high ; int t= a[i]; while(i<j) {
while(i<j&&a[j]>t) j--; a[i] =a[j];
while(i<j&&a[i]<=t) i++; a[j] =a[i];
a[i] =t; quick_sort(a,low,i-1); quick_sort(a,i+1,high); } } <quote> why does the code do this, esp. after the second while-statement the assignment"a[i]=a[j]",and the third while-statement the assignment "a[j] =a[i]"? I m very confused.Any reply is appreciated.Thanks.
You're question isn't really about C, but it's about the algorithm.
One way to view it is that it is breaking the list into 2 pieces based
on the first entry. One piece has entries that are all less than the
first, and the 2nd piece has entries all greater than the first (that's
not quite true, but I think it makes it easier to grok the solution if
you think that way temporarily.) It might be instructive to consider a
simple example. Suppose your list has 10 entries:
3,2,0,8,7,5,1,4,9,6
The first loop moves j down until a[j]==1, then the assiigment a[i] =
a[j] creates:
1,2,0,8,7,5,1,4,9,6
You now increment i until a[i] == 8, and the assignment a[j]= a[i]
makes:
1,2,0,8,7,5,8,4,9,6
Now, a[i] = t makes the list:
1,2,0,3,7,5,8,4,6
The net effect is that the value that was at the start of the list (3)
is now in the middle of the list and the list has the property that
everything to the left of the 3 is less than 3 and everything to the
right of the three is greater than 3. You then recursively sort each
half.
Now, what I said above is not quite correct. For this case, it happens
that the list satisifies the very nice property of being ordered w.r.t.
the first entry. However, you'll notice that we never looked at the 7
or the 5. Suppose the 5 had been a 2 instead. In that case, the list
would now look like:
1,2,0,3,7,2,8,4,6.
After you do the recursion, the list will look like:
0,1,2,3,2,4,6,7,8,
with i indexing the 3 and j indexing the 6. Notice that outside of
those bounds, the list is ordered correctly. The purpose of the outer
while loop is to squeeze i and j together until the entire list is
ordered properly.
Bill Pursell wrote: pinkfog wrote: Hello,all I m just a newbie to c,and now i m learning quick sorting,i dont very undertand this algorrithm,can someone kind to explain it to me? the code: <quote> void quick_sort(int a[] ,int low ,int high) { int i =low; int j =high ; int t= a[i]; while(i<j) {
while(i<j&&a[j]>t) j--; a[i] =a[j];
while(i<j&&a[i]<=t) i++; a[j] =a[i];
a[i] =t; quick_sort(a,low,i-1); quick_sort(a,i+1,high); } } <quote> why does the code do this, esp. after the second while-statement the assignment"a[i]=a[j]",and the third while-statement the assignment "a[j] =a[i]"? I m very confused.Any reply is appreciated.Thanks.
You're question isn't really about C, but it's about the algorithm. One way to view it is that it is breaking the list into 2 pieces based on the first entry. One piece has entries that are all less than the first, and the 2nd piece has entries all greater than the first (that's not quite true, but I think it makes it easier to grok the solution if you think that way temporarily.) It might be instructive to consider a simple example. Suppose your list has 10 entries: 3,2,0,8,7,5,1,4,9,6 The first loop moves j down until a[j]==1, then the assiigment a[i] = a[j] creates: 1,2,0,8,7,5,1,4,9,6 You now increment i until a[i] == 8, and the assignment a[j]= a[i] makes: 1,2,0,8,7,5,8,4,9,6 Now, a[i] = t makes the list: 1,2,0,3,7,5,8,4,6 The net effect is that the value that was at the start of the list (3) is now in the middle of the list and the list has the property that everything to the left of the 3 is less than 3 and everything to the right of the three is greater than 3. You then recursively sort each half.
Now, what I said above is not quite correct. For this case, it happens that the list satisifies the very nice property of being ordered w.r.t. the first entry. However, you'll notice that we never looked at the 7 or the 5. Suppose the 5 had been a 2 instead. In that case, the list would now look like: 1,2,0,3,7,2,8,4,6. After you do the recursion, the list will look like: 0,1,2,3,2,4,6,7,8, with i indexing the 3 and j indexing the 6. Notice that outside of those bounds, the list is ordered correctly. The purpose of the outer while loop is to squeeze i and j together until the entire list is ordered properly.
Thanks for your explaination.
-----------------------------pinkfog--------------------------------------- This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Pjotr Wedersteers |
last post by:
Hello,
I took quite elaborate SQL and SQL-admin courses at Oracle, but that was
years ago. Have never since used SQL but for some extremely simple
straightforward queries on single table db's....
|
by: Greg Bryant |
last post by:
I'm a bit confused about image_graph - I'm just trying to create a line
graph with multiple lines, be able to assign the text for the x and y ticks
and colors for the lines. A legend would be...
|
by: Snake |
last post by:
Hello guys,
I have a quick question about pointers.
When I say
int *p;
*p = 40;
cout << *p;
why does that produce and error message(something about fault address)?
Isnt that I created a...
|
by: A.M |
last post by:
Hi,
I uderstand any Quick Start samples in .NET documentation or VS.NET
documentation or in any other community/portal websites, is a link to
http://samples.gotdotnet.com/quickstart/.
That...
|
by: Rider |
last post by:
Hi, simple(?) question about asp.net configuration..
I've installed ASP.NET 2.0 QuickStart Sample successfully. But, When I'm
first start application the follow message shown.
=========
Server...
|
by: Steven Nagy |
last post by:
Hi all,
Sorry I have no time to test this myself....
Can I add the same attribute to a field twice?
Eg.
Public string myField;
|
by: Joel Hedlund |
last post by:
Hi!
There's one thing about dictionaries and __hash__() methods that puzzle me. I
have a class with several data members, one of which is 'name' (a str). I would
like to store several of these...
|
by: stacey |
last post by:
Hi all,
I have a quick question about form classes. I am following this
tutorial: http://www.evolt.org/article/PHP_Login_System_with_Admin_Features/17/60384/index.html
Basically, it is a login...
|
by: sukatoa |
last post by:
1. when we initialize value,
String st = new String("the quick brown fox jump over the lazy dog");
and
String st = "the quick brown fox jump over the lazy dog";
both of them are...
|
by: Anthony P. |
last post by:
Hello Everyone,
I'm writing an application that, so far, only has three forms:
frmSplashScreen
frmLicenseScreen
frmConfigurationScreen
Now, frmSplashScreen has a timer that sits it on...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |