vizskywalker
Mar 7 2005, 05:55 PM
Okay, I'm not looking for code here, just the steps the algorithem would go through. I am trying to find the fastest algorithem to sort a list of elements. So far the fastest I have come up with is as follows (demonstrated on a five element list). Step List Procedure 0 dbace this is the starting list 1 bdace compare spots 1 and 2, switch if necessary 2 bdace compare spots 5 and 4, switch if necessary 3 adbce compare spots 1 and 3, switch if necessary 4 adbce compare spots 5 and 3, switch if necessary 5 adbce compare spots 1 and 4, switch if necessary 6 adbce compare spots 5 and 2, switch if necessary 7 abdce compare spots 3 and 2, switch if necessary 8 abcde compare spots 3 and 4, switch if necessary 9 abcde compare spots 3 and 2, switch if necessary (this last step is needed occasionally even though it appears redundant) If you have a faster method or comments on this one, I'd love to see it. The purpose here is to find an algorithem that can be aplied to any language.
Reply
qwijibow
Mar 11 2005, 05:01 PM
Looks confusing, the nodes you compare seem random ? it would be hard and ocnfusing to actually implement that. Why not use Bubble sort ? although you are not looking for code, its easyer to explain with code... i hole you understand. CODE // sort characters in a string into alphabetical order (must be lovercase)
const int MAX=10; char array[MAX];
bool chaned=true;
//TODO: Code to fill array with MAX-1 random characters
while(changed) { // (if changed is false, the list is already in order) changed=false; // reset variable for(int n=0; n<MAX-1; n++) {
if( array[ n ] > array[ n+1 ]) { // TODO: swap the 2 characters over changed = true; (we made a change, so we are not in order) } } }
// String is sorted !
Reply
vizskywalker
Mar 11 2005, 05:57 PM
The problem with Bubble sort is that it has the potential to take twice as long. If we assume that each step takes up one unit of time, then all of the checks add up and make the time twice as long. I do admit that Bubble sort has the potential to be very fast, and may actually be the best option. I'm still looking for a method with a definite short amount of time. And my method isn't random, it is the same principle as sort spot 1, then spot 2, then spot 3, et.c, except running from both ends at the same time.
Reply
Dizasta
Apr 5 2005, 08:55 AM
so what happens when the list is already sorted to start with?
Reply
vizskywalker
Apr 5 2005, 11:27 AM
For Bubble sort it stops early, and for my method, it goes through the steps and just doesn't switch anything. But I took another look at BubbleSort and continued the experimentation with my method, and for large numbers of items, my method quits being as effective, and with a couple modifications done to the assembly code BubbleSort becomes really fast and can take at most about 1.5 times as long instead of 2 times as long.
Reply
FearfullyMade
Apr 9 2005, 03:28 PM
I would suggest that you look into a sorting algorithm like quicksort. Bubblesort is actually a very slow algorithm, its running time is N^2 (N is the number of elements in the list). The running time for quicksort, on the other hand, is N log N. The only drawback of quicksort is it is a little more complicated to write. Here are the basic steps: 1. Choose one element at random 2. Split remaining elements into two groups as follows: Compare each remaining element with chosen one Put smaller elements to left of chosen one Put larger elements to right of chosen one 3. Repeat step 2 for all subgroups 4. When all groups have one element, they are in ascending order I'm sure that if search for quicksort on the interent you can find examples of it (and probably a better explaination than the one I gave). I hope this helps.
Reply
vizskywalker
Apr 10 2005, 09:10 PM
Thanks, I knew bubblesort was slow, but the more I looked at the code the less I could figure out why. Your instructions actually made sense, so I don't think I will have to do an internet search. ~Viz
Reply
iamrockandroll13
Apr 22 2005, 11:51 PM
QUOTE(FearfullyMade @ Apr 9 2005, 11:28 AM) I would suggest that you look into a sorting algorithm like quicksort. Bubblesort is actually a very slow algorithm, its running time is N^2 (N is the number of elements in the list). The running time for quicksort, on the other hand, is N log N. The only drawback of quicksort is it is a little more complicated to write. Here are the basic steps: 1. Choose one element at random 2. Split remaining elements into two groups as follows: Compare each remaining element with chosen one Put smaller elements to left of chosen one Put larger elements to right of chosen one 3. Repeat step 2 for all subgroups 4. When all groups have one element, they are in ascending order I'm sure that if search for quicksort on the interent you can find examples of it (and probably a better explaination than the one I gave). I hope this helps. Is this basically a binary search based sorting algorithm? if so, that puts it at a running time of O(ln N) which is definately better than O(N^2)
Reply
FearfullyMade
Apr 23 2005, 04:45 AM
Quicksort does have a lot in common with the binary search algorithim. The basic idea of both is splitting the list in half multiple times. I can't remember for sure why quicksort is O(N In N) while binary search is O(In N). I believe it has something to do with the fact that with quicksort you have to compare items at each step and then move them around. I don't learn why algorithims like quicksort work like they do until next semester, so that might not be right. BTW, I noticed in my earlier post I used log in the running time of quicksort. I meant log base 2 when I put log.
Reply
vizskywalker
Apr 23 2005, 04:53 AM
I figured you meant log base 2, we are after all, essentially dealing with binary. Thanks for all the help with this algorithm, I will probably have another algorithm question soon, os keep your eyes open. ~Viz
Reply
Latest Entries
evought
May 10 2006, 01:03 AM
qsort or quicksort is already implemented in many languages or their add-on libraries (e.g. C++ STL, Java, Python, Ruby) there is seldom a need to write your own sort method these days unless it is just as a learning exercise. Note that many of these libraries come with source code if you want to look at how they are done.
Reply
BitShift
May 10 2006, 12:51 AM
Many programmers consider the quicksort to be the fastest sorting algorithm available. Technically its not. There is a sort called the Merge Sort which takes a recursive means of sorting. Let me give you a comparison. I hope you understand Big O notation, its pretty easy. Bubble Sort: - Data are in completely random order: O(n^2)
- Data are ordereed from lowest to highest: O(n)
- Data are ordered from highest to lowest: O(n^2)
Insertion Sort: - Data are in completely random order: O(n log(n))
- Data are ordereed from lowest to highest: O(n)
- Data are ordered from highest to lowest: O(n log(n))
-I'm not 100% sure that these are the correct Big O runtimes for the Insertion sort. Quick Sort: - Data are in completely random order: O(n log(n) )
- Data are ordereed from lowest to highest: O(n^2)
- Data are ordered from highest to lowest: O(n^2)
Merge Sort: - Data are in completely random order: O(n log(n) )
- Data are ordereed from lowest to highest: O(n log(n) )
- Data are ordered from highest to lowest: O(n log(n) )
As you can see, the Bubble sort is only good, when the list is already sorted. However your not going to sort an already sorted list. The Quick sort is awesome when the list is random. However, if the list isn't completely random, and is only off by a few elements, it takes longer. The Merge sort is consistent, providing O(n log(n) ) If you don't know, "n" is the number of elements in the list you are sorting. People say the Quick Sort and Binary Search are related, because Binary Search uses the same technique and a Binary Search also has O(n log(n) ). I have no code on the merge sort in any language I just know its there. One of the reasons that the Merge Sort proves to be more effective then the Quick Sort is that the Quick Sort is implemented in such a way to save Memory. The Merge Sort uses a recursive method and therefore, uses a ton of memory. The Insertion sort looks better then the Merge sort, but I'm not 100% sure that I have the correct Big O runtimes for the insertion sort. Anyways, I just posted this because I wanted to share information that I had.
Reply
wykurz
Jul 19 2005, 07:02 PM
i think that in most cases the best choice is to use common library algorithms, like C++ quicksort. it's a very smart modification of insertion sort (much better than bubble sort, because it leaves the same element's in order they were in the beginning) and original quicksort. takes one line to write it. if you don't want to use libraries, you can easily write insertion sort. works pretty fast with lists up to 50 elements (if larger think about QS). if sorting integers from a certain range you can use algorithm that would work in O(n) (easy to guess how it works, i hope  ) if you're just interested in theoretical algorythmic aspect of how fast can i sort a list of X elements (where X is constant), than it's quite easy to think out how can you do it with list of up to 6 elements. for a list of 24 elements it took 3 weeks to compute the result with 3 PCs (pentium III 1GHz). regards
Reply
mdchurchill
May 27 2005, 10:43 AM
Quicksort is average O(log N) time, but at worst O(N^2) if the data is annoyingly constructed. There are algorithms that run in more consistent log time (e.g. mergesort, heapsort) but there algorithms are much simpler. Well definately in the second case. In the former case (in Haskell notation which is so beautiful I AM introducing these forums to the lovely world of FP): Merge (x:xs) (y:ys) = if (x < y) then x:Merge(xs, y:ys) else Merge [] ys = ys Merge xs [] = xs MergeSort xs = Merge (Mergesort ys) (MergeSort zs) where ys = odds xs zs = evens xs odds (x:y:xs) = x:odds(xs) odds [x] = x odds [] = [] evens (x:y:xs) = y:evens(ys) evens [y] = [] evens [] = [] Where here x:xs represents x at the front of a list of xs, [] the empty list and [] the singleton list. (In other words - to sort a list [3,2,4,1] we split into odds and evens - [3,4] and [2,1], then sort these recursively into [3,4] and [1,2] and then Merge them together into [1,2,3,4]. Merge takes to (ordered) lists and produces an (ordered) list by looking at the first element of both (see above.))
Reply
Recent Queries:--
tournament sort source codes - 7.05 hr back. (1)
-
tornament sort in c - 7.85 hr back. (1)
-
linking to c :quicksort using assembly - 18.24 hr back. (1)
-
python list sort big o notation - 28.54 hr back. (1)
-
tournament sort c code - 29.53 hr back. (1)
-
what is tournament sort explain with example - 45.52 hr back. (1)
-
insertion, bubble,selection sort assembly codes - 52.11 hr back. (1)
-
write an assembly language program to sort the numbers in an array in descending order using bubble sort method - 95.51 hr back. (1)
-
compare theoretical running time with quicksort results - 107.75 hr back. (1)
-
python sort numbers lowest to highest - 133.87 hr back. (1)
-
tournament sort c - 139.13 hr back. (1)
-
algorithm tournament sort c code - 139.21 hr back. (1)
-
sorting multiple choice questions - 170.33 hr back. (1)
-
alphabetical sort method for list in python - 198.43 hr back. (1)
Similar Topics
Keywords : sorting, list, algorithem, search
- Download From Ftpz, Using Ftp Search Sitez
Download From Ftpz, Using Ftp Search Sitez (0)
Homepages Friends
Get PAID to search! (5) I recently signed up for "Homepages Friends", a program which pays you about €0.02 for every search
you make using their version of Yahoo. The system is very easy to use, as you simply add the toolbar
to your browser (or you can do it online instead - either way no download is needed). I have yet to
cash out, as the minimum is €20, and I only have about €2. However, if you are an avid searcher, or
if you're simply willing to spend a lot of time working on it, you can EASILY get €4 + a day.
Also, you can invite friends and get a portion of their intake (I believe it....
How To: Display A Members/user List.
With PHP, Mysql, and HTML. (3) Alright, some of you might want to display your User's or Members on your site. Notes: 1.This
is to fit in with Feelay's register and Log-in scripts you can find in the tutorial section. 2.I
made this to show the members of my site who is a member and what their ID is. First off, we must
set up a connection to our MySQL Database. CODE <?php $con =
mysql_connect("localhost","database_username","database_username_password
4;); if (!$con) { die('Could not connect: ' .
mysql_error(....
Yahoo! Search Boss
(5) Last wednesday (2008-07-09) Yahoo! Search launched a new service called Yahoo! Search
BOSS (Build your Own Search Service) which is a web services platform that allows developers and
companies to create and launch web-scale search products by utilizing the same infrastructure and
technology that powers Yahoo! Search . Some capabilities of the new Yahoo! Search BOSS
service are: Ability to re-rank and blend results Unlimited queries Total flexibility on
presentation This service is based on Python and is available to everybody, to get started a....
Search Engine Keyword Position
(0) So many keywords, so little time -trying to keep track of your site's ranking for every phrase
can get pretty hectic. That's even more true if you intend to keep tabs on multiple search
engines. Luckily, the Search Engine Keyword Position tool can help. The Search Engine Keyword
Position tool is very easy and simple, you only need to enter your site's address and a key
word or phrase, and it will determine where you stand with Google , Yahoo , and MSN . Best
regards,....
Get Paid To Search Yahoo!
New way for you to make money online (10) Hi buddies, Is this a good news for you? I've got paid for the first month from this site. Here
is how you can earn: After you sign up, they ask you to set their page as homepage and install a
search box.Everyday, when you search once, you will earn up to 3p. How much you can earn depends on
where you live. I earned 1.5p per search. So, if you search 40 times per day, how much you will earn
a month? It's very easy, right? In addition, when you refer friends, you will earn more. They
offer 4 referral levels: 50%, 10%, 5% and 2.5%. If you are interested, sign up a....
New Games.
Looking for a list of Brand New Games. (0) I have just recently stumbaled upon asroempiers just as it was lunching a new server, i thought this
was great untill my newbiness got the better of me and it soon became very hard work. I was
woundering if there was any games that have just been lunched or are being alpha testing so that i
would be in the same boat as everyone.....
Spider Simulator Tool
See your content the way the search engines do (0) The Spider Simulator tool will help you to see your content the way the search engines do!
Spiders don't operate like normal users, and yet you've got to take their perspective into
account. Just enter the URL in which you're interested, and the Spider Simulator tool will
return "spidered" page titles, text, meta descriptions, meta keywords, internal links, and external
links. Use this information to your advantage and gain new insight into how the search engines work.
QUOTE A lot of content and links displayed on a web page may not actually be....
List Of Free Mmos
(1) I thought I'd make a list of a few of the free MMOs I'm aware of. I know there are more but
I can't think of any specifics at the moment, so I will add to the listing later. Fly For Fun
is a 3D cartoony MMO, it seems to be fairly successful. I don't know a whole lot about it but
there's some general info on Wikipedia Fury is a 3D entirely PvP-centric MMO that was
released as a retail game, but due to some unpopular changes made to the game it lost alot of its
fan-base. It was extremely successful during beta and its initial stages, but no lo....
Some Usefull Linux Basic Commands And Utilities. Please Add To This List If You Know One.
(0) Let me give some usefull linux commands and utilities. Please add to this list if you know.
Work with tar files. To make tar archive use $ tar -cvf filename.tar
filename To extract tar archive use $ tar -xvf filename.tar To
extract tar archive with gz use $ tar -xzvf filename.tar.gz Connect to remote
system through ssh $ ssh name@ip followed by passwd e.g. ssh
project@172.16.0.14 passwd: List the file in current directory $ ls -l
l....
Url Rewriting Tool
Useful tool for achieving Search Engine Success (0) I receive the last email from the Jayde Listing Notes list some days ago and with it comes an
excelent SEO tool called URL Rewriting Tool which i think is very useful and i want to share with
everybody. This useful tool allows you to convert your dynamic URLs into static looking html URLs,
it is extremely easy to use, is than simple than entering a dynamic URL into a text box and press a
submit button, once you do it the URL Rewriting Tool returns two type of results: Single Page URL
Directory Type URL For each type of result the URL Rewriting Tool will generat....
My List Of Topics And Posts
(5) How can i save all the topics and posts i made??? I know that i can do it by accesing my control
panel and then save the complete page but what i need is just only the list of this information, is
there a way to get this as a HTML file only or better yet as a CVS file??? Hope i'm posting in
the correct place, if not, please move it to the best place. Best regards,....
Cutenews 1.4.5 Security Alert Regarding Search.php
please update your file immediately (1) Searching through our forum, I came across few posts mentioning "my site was hacked" while using
CuteNews. So before I made this post I wanted to be sure if everyone here knew about CuteNew's
serious vulnerability by searching our forum. I am also a victim of recent vandalism by someone from
Germany who knew about this exploit. Please read Cutenews for clear understanding how, why and
how-to. If you are using CuteNews as CMS for your site please visit the above URL and
countermeasure for your CuteNews script. It looks like this information has been available sin....
Live Search Webmaster Center
(1) I find that it is very useful in many ways. My site is now included in the listings and if you type
the name of m,y site it's the first link. I've used the yahoo webmaster tools (site
explorer), google webmaster tools and Live search webmaster tools. I think that the Live search one
is better. Yahoo is useless and google is ok but hard to get into listings. This is only my opinion.
What do you think of Live Search webmaster central?....
Do Google Search Better Than Yahoo?
This is a question for you all google users!! (15) Do you think google search is better than yahoo?? Are they have similar search?? Well for me google
search is more effective than yahoo search engine.....
Google- Changing The Search Preferences!
(3) If you want the google site to block more sites, then you will need to go onto the google site. Then
go onto preferences. There you can change alot .For example the language it should search for only,
or if the result window should be seperate, or how many results should be displayed per site. This
window to change preferences is very useful! Have fun!....
Windows Live Search
The future of MSN Search (14) I have used Windows Live Search for that contest that MSN hosted a few months ago (can't
remember if it was a year). It works if you have the BETTER keywords to search with, otherwise it
doesn't work that well. It is my preferred ALTERNATE search engine (my favourite is
Google+Yahoo). MSN Search doesn't work that well. It doesn't come up with that many results
and Yahoo! generally searches better than it. I don't use MSN Search anymore. After all,
Windows Live Search will replace it! /smile.gif" style="vertical-align:middle" emoid=":)" borde....
Orkut.com Auto Scrapper - Scrap Ur Friend List In One Go
For the Orkutters (12) hi fellas, as most orkutters know that u cant scrap ur whole friend list in one go. i cant keep
my friends up to date with myself (since they dun know whats a blog) so i have to scrap them all
individually. having 100+ friends i decided to use an autoscrapper and came across Scrapboy.
bugged up with Scrapboy's bulky interface and huge download size, i decided to code my own auto
scrapper for Orkut.com If you don't know what it is, hit the following link
http://www.captainron.uni.cc/orkutter (click download to download) its around 570Kb in download
and ....
A List Abosulutely Free MMORPGs
Thats right FREE! (5) Here is a list of MMORPG i have collected, they are all absolutely free! note: sry theres no
Pictures or direct links (to find the website, just search it up on google) The pricing of these
game may change (as in become frome free to pay to play) ___________ Gunbound Rakion Runescape
Pristontale (free til lvl 40) Auditon Online Dance Battle (online version of DDR) Holy Beast
Online Dream Of Mirror Online Guild Wars (not free, you need to buy the game, but no monthly
fees) Lineage 2 (the retail version is not free, although there are very advance priva....
Singingfish
Music Search... (3) If you want the best music search on the net, go to www.singingfish.com . Wow. /smile.gif"
style="vertical-align:middle" emoid=":)" border="0" alt="smile.gif" /> I find all my music through
it. And now AOL owns it. /tongue.gif" style="vertical-align:middle" emoid=":P" border="0"
alt="tongue.gif" /> Help yall? -Josh....
List Of Free MMORPGs
(18) I wrote this a while ago With the help of some people If you have any questions or anything Message
Me! 5 Masters Online strategy game. AdventureQuest AdventureQuest is a free lunch break
sized RPG that you can play daily using your web browser. We are adding new things every week!
Join us in shaping the direction of this campy yet addictive role playing game. Alien Assult
Traders Alien Assault Traders is a multiplayer turn based space trading game. Where players use
turns that are accumilated over time to trade good and build empires and take over the ....
Blingo Search Engine
A SE that gives away random prizes (3) A friend told me about a search engine that brings back Google results, however the owners of the
Engine have the site set up to give random prizes away depending on what "turn" you are to search.
They pick a bunch of random winning times, and if you search at the right time, you win a gift
certificate, or other prize. The theory is, that if you DO happen to hit your search on one of
these "winning times", instead of being redirected to your search results, you are notified that you
have won, and they send you your gift somehow... I have never won on this thing and I ....
Search Engine Website - What Makes Them Famous ?
HOw come?? (8) Why is Yahoo! and Google so famous? What makes them stand out among the rest of the search
engines? There are some other search engines like catcha.com.my or even msn.com....
How Search Engines Operate
answering your questions (6) When I took a computer class, they said that search engines use "spiders" to register your site and
have it show up when you type a keyword. I'm pretty sure this is true, coming from a professor
with a degree in Computer Science but I'm wondering, what exactly are what they call spiders?
What are spiders hosted on and all the technical questions. If you know anything technically about
specifically how search engines like Google functions, this is the thread for you. So, please -
share what you know. Your honest patronage is greatly appreciated and will be listene....
Mud List
Peoples favourite MUDs (11) I am currently an Immortal (member of staff) on a new MUD, IahMUD. It is not entirely open to the
public yet, but hopefully it will be soon. We have a number of good coders and builders so it should
turn out well. If you are interested you should check out the website: www.iahmel.com A great MUD in
the making.......
Comprehensive List Of Resources On Graphics/design
All of you should contribute (12) HI all, This is what my plan is... We've got hundreds of posts on good graphics and design
site links all spread across multiple posts, some of which just age out and fall to the bottom of
the list and then there are reposts on the same topic again. My plan is to come up with some such
good lists with contributions from all of you. But instead of having the links spread across
multiple posts or replies to this topic, I'll merge your posts into ONE BIG POST with all the
links presented serially - making it much easier for our readers to find out...as well as....
Array Sorting
Does anyone hava a decent JAVA method (21) does anyone have a decent JAVA method that will sort an array from smallest-to highest?
/mellow.gif" style="vertical-align:middle" emoid=":mellow:" border="0" alt="mellow.gif" /> The one
i'm trying to write doesn't seem to work... or if you could look at mine below, and tell me
what i did wrong, that'd be nice to.(if it reallllyyyyyyyyy sucks, please dont laugh to loud
/biggrin.gif" style="vertical-align:middle" emoid=":D" border="0" alt="biggrin.gif" /> ) This should
take an array and then calculate how many of a number is in it, add it to the first slots....
List Of Free Mmorpg..
(21) Do enjoy this list /wink.gif' border='0' style='vertical-align:middle' alt='wink.gif' /> (ALl
these are games i have played b4 and are still free): www.runescape.com This game is so called "3D"
.. although i looks like it, i don't feel it is 3D /tongue.gif' border='0'
style='vertical-align:middle' alt='tongue.gif' /> .. this is a quite a fun game actually. I played
this game actually 2 years back. You can do lots of things like mining, blacksmithing, fishing and
there are many quests in this game. Very typical MMORPG /smile.gif' border='0' style='vertical-ali....
Add A Search Box To My Web Site
how to? (10) I don't know If this topic I should post here, but I'll try! I have a web site and i
really need to add to my website a feature like searching on the site!I need a simple text boxt
and a button, that will search the site content! are there already done version of such
programs? pleasee help! thanks you!....
You can Play now in Linux
These is a list of the games. (26) You can Play a greates gameg in linus as: Unreal Tournament Quake 3 Wolfenstein Enemy teritory Medal
of Honor And Emule Nintendo 64 and Play Station games. He have your property games as: Tux Raser
Tux Cart Flith of the amazon queen Beneath a Steel Sky and most more.....
Looking for sorting, list, algorithem, search
|
|
Searching Video's for sorting, list, algorithem, search
|
advertisement
|
|