Clump Sort

In: Computers and Technology

Submitted By mushaidh
Words 1753
Pages 8
2010 Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation

Clump Sort: A Stable Alternative To Heap Sort For Sorting Medical Data
Visvasuresh Victor Govindaswamy
Computer Science Texas A&M University-Texarkana Texarkana, USA lovebat814@yahoo.com

Matthew Caudill
Computer Science Texas A&M University-Texarkana Texarkana, USA

Jeff Wilson
Computer Science Texas A&M University-Texarkana Texarkana, USA

Daniel Brower
Computer Science Texas A&M University-Texarkana Texarkana, USA

G. Balasekaran, FACSM
Medical and Sports Science Nanyang Technology University Singapore

Abstract—Sorting data sets are a thoroughly researched field. Several sorting algorithms have been introduced and these include Bubble, Insertion, Selection, Shell, Quick, Merge and Heap. In this paper, we present a novel sorting algorithm, named Clump Sort, to take advantage of ordered segments already present in medical data sets. It succeeds in sorting the medical data considerably better than all the sorts except when using totally non-clumped data. In this test using totally nonclumped data, Heap sort does only slightly better than Clump sort. However, Clump sort has the advantage of being a stable sort as the original order of equal elements is preserved whereas in Heap sort, it is not since it does not guarantee that equal elements will appear in their original order after sorting. As such, Clump Sort will have considerably better data cache performance with both clumped and non-clumped data, outperforming Heap Sort on a modern desktop PC, because it accesses the elements in order. Sorting equal elements in the correct order is essential for sorting medical data. Keywords-algorithms; design; experimentation; performance

I.

INTRODUCTION

Bubble sort, one of the simplest and one of the slowest, is a famous example used for teaching…...

Similar Documents

Universe

...faster and faster. That's like tossing an apple upward and it goes up faster and faster. Now if you saw an apple do that, you'd want to know why. What's pushing on it? Similarly, the astronomers' results are surely well-deserving of the Nobel Prize, but they raised an analogous question. What force is driving all galaxies to rush away from every other at an ever-quickening speed? Well the most promising answer comes from an old idea of Einstein's. You see, we are all used to gravity being a force that does one thing, pulls objects together. But in Einstein's theory of gravity, his general theory of relativity, gravity can also push things apart. How? Well according to Einstein's math, if space is uniformly filled with an invisible energy, sort of like a uniform, invisible mist, then the gravity generated by that mist would be repulsive, repulsive gravity, which is just what we need to explain the observations. Because the repulsive gravity of an invisible energy in space -- we now call it dark energy, but I've made it smoky white here so you can see it -- its repulsive gravity would cause each galaxy to push against every other, driving expansion to speed up, not slow down. And this explanation represents great progress. But I promised you a mystery here in part one. Here it is. When the astronomers worked out how much of this dark energy must be infusing space to account for the cosmic speed up, look at what they found. This number is small. Expressed in the relevant......

Words: 3198 - Pages: 13

Given the Sorts of Personal Relations We Now Enter Into, and the Demands of the World of Work and the Influences of the Digital Age, It Is No Longer Possible to Become an Educated Person in Such a Troubled World. True or False?

...Given the sorts of personal relations we now enter into, and the demands of the world of work and the influences of the digital age, it is no longer possible to become an educated person in such a troubled world. True or false? We live in an increasingly complex world of rapid change and can only begin to imagine what the future will look like. It is also a very troubled world in which we are confronted daily with a myriad of challenges. The sheer scale of information and social constraints threaten to overwhelm us and we may be justified in thinking that it is no longer possible to become an educated person. Contrary to this view, however, I believe that it is not only possible, but also imperative that we do so if we are to both survive and thrive in the modern world. Any rewards will outweigh the challenges. The real question is not really whether it is possible to become and educated person, but exactly what that education should look like in such a climate? Education is highly valued universally and the sphere of education today is extensive. In most countries, in addition to a developed system of state schooling, there is an expanding system of private schooling. This has arisen in response to the growing demand for qualifications and accreditation in an increasingly diverse range of professions. However, being an educated person today is not simply about possessing knowledge. The educated person is one who is able to utilise knowledge and apply it productively...

Words: 703 - Pages: 3

Quick Sort Analysis

...Here is an analysis of the time complexity of quick-sort in detail. In quick sort, we pick an element called the pivot in each step and re-arrange the array in such a way that all elements less than the pivot now appear to the left of the pivot, and all elements larger than the pivot appear on the right side of the pivot. In all subsequent iterations of the sorting algorithm, the position of this pivot will remain unchanged, because it has been put in its correct place. The total time taken to re-arrange the array as just described, is always O(n)1 , or αn where α is some constant [see footnote]. Let us suppose that the pivot we just chose has divided the array into two parts - one of size k and the other of size n − k. Notice that both these parts still need to be sorted. This gives us the following relation: T (n) = T (k) + T (n − k) + αn where T (n) refers to the time taken by the algorithm to sort n elements. WORST CASE ANALYSIS: Now consider the case, when the pivot happened to be the least element of the array, so that we had k = 1 and n − k = n − 1. In such a case, we have: T (n) = T (1) + T (n − 1) + αn Now let us analyse the time complexity of quick sort in such a case in detail by solving the recurrence as follows: T (n) = T (n − 1) + T (1) + αn = [T (n − 2) + T (1) + α(n − 1)] + T (1) + αn (Note: I have written T (n − 1) = T (1) + T (n − 2) + α(n − 1) by just substituting n − 1 instead of n. Note the implicit assumption that the pivot that was chosen divided the......

Words: 1014 - Pages: 5

A Tale of Three Lions

...it was, Mr. Tom,' I went on, with my politest air, although in agony from the nugget underneath—for I hold it is always best to be polite to a man who is so ready with a handspike—'my boy and I have had a slight difference of opinion, and I was enforcing my view of the matter upon him; that's all.' "'Yes, Mr. Tom,' put in Harry, beginning to weep, for Harry was a smart boy, and saw the difficulty we were in, 'that was it—I halloed because father beat me.' 9 "'Well, now, did yer, my dear boy—did yer? Well, all I can say is that a played-out old claim is a wonderful queer sort of place to come to for to argify at ten o'clock of night, and what's more, my sweet youth, if ever I should 'ave the argifying of yer'—and he leered unpleasantly at Harry—'yer won't 'oller in quite such a jolly sort 'o way. And now I'll be saying good-night, for I don't like disturbing of a family party. No, I ain't that sort of man, I ain't. Good-night to yer, 'unter Quatermain—goodnight to yer, my argified young one;' and Mr. Tom turned away disappointed, and prowled off elsewhere, like a human jackal, to see what he could thieve or kill. "'Thank goodness!' I said, as I slipped off the lump of gold. 'Now, then, do you get up, Harry, and see if that consummate villain has gone.' Harry did so, and reported that he had vanished towards Pilgrim's Rest, and then we set to work, and very carefully, but trembling with excitement, with our hands hollowed out all the space of ground into which I had......

Words: 12799 - Pages: 52

Use the Concepts Described in the Course to Analyze What Sort of Innovation This Is and How It Compares to Competing Products or Processes

...a selling area of 821,100 square meters around the world. With sales of 3.7 billion dollars in the business year 2005, Zara had developed into Spain’s the most famous fashion brand and the leading brand of Inditex (Kumar, 2006). Zara is one of the most outstanding apparel retail businesses in the world today. Although it is not the biggest, its marginal profits and rates of growth are leading the industry. The purpose of this essay is to analyze what sort of innovation Zara used on its way to success and make comparisons of competing products or processes with its competitors. By analyzing and comparing, it is obvious that the company's success depends on conducting a series of innovations at each one of the parts in the business: fashion-forward design, unique branding strategies, in-house production processes and centralized distribution system. Basically, this essay has been divided into four parts: the first part focus on describing how Zara makes its designs more innovative compare with other appeal retailers. Then, what sort of innovation used in their branding strategies will be discussed. Next, it will consider Zara’s innovation of production process and show an apparent difference of this process among Zara, H&M and the Gap. Finally, it will look at how Zara promotes innovation on their distribution process in to become more fast. It is those innovations that set challenges for rivals since Zara’s business model is extremely difficult to imitate or equal and also......

Words: 2808 - Pages: 12

Quick Sort Algorithm

... Quick Sort Implementation Next, recall that our goal is to partition all remaining elements based on whether they are smaller than or greater than the pivot We will find two entries: – One larger than the pivot (staring from the front) – One smaller than the pivot (starting from the back) which are out of order and then correct the ordering – I.e., swap them 1 7.6.5 Quick Sort Implementation Continue doing so until the appropriate entries you find are actually in order The index to the larger entry we found would be the first large entry in the list (as seen from the left) Therefore, we could move this entry into the last entry of the list We can fill this spot with the pivot 2 7.6.5 Quick Sort Quick Sort Example First, we examine the first, middle, and last entries of the full list The span below will indicate which list we are currently sorting 3 7.6.5 Quick Sort Quick Sort Example We select 57 to be our pivot – We move 24 into the first location 4 7.6.5 Quick Sort Quick Sort Example Starting at the 2nd and 2nd-last locations: – we search forward until we find 70 > 57 – we search backward until we find 49 < 57 5 7.6.5 Quick Sort Quick Sort Example We swap 70 and 49, placing them in order with respect to eachother 6 7.6.5 Quick Sort Quick Sort Example We search forward until we find 97 > 57 We search backward until we find 16 < 57 7 7.6.5 Quick Sort Quick Sort......

Words: 1243 - Pages: 5

Sort Paper

...Short Paper At the creation of the United States, the states were assumed to have the power and authority of self-governing nations. Each state has the general power to protect the health of its population within its geographic borders as long as the laws do not obstruct the rights of individuals guaranteed by the constitution. The federal government regulates health matters through the powers granted to the federal government in the federal constitution. This allows the federal government to create benefit programs and to indirectly regulate local activities that it would not have the authority to regulate directly. For example, the federal government created the Medicare program to pay for health care for the elderly and disabled, and Medicaid to pay for health care for the poor. Health care institutions that receive federal money in payment for services to Medicare and Medicaid recipients have to abide by federal regulations in order to keep receiving federal funds. According to Pozgar (2012), “a tort law is a civil wrong, other than a breach of contract, committed against a person or property for which a court provides a remedy in the form of an action for damages”. Within the general field of health care there is a good deal of discussion of tort law and health care because tort actions comprise what are more commonly known as medical malpractice or medical negligence actions. A medical malpractice or medical negligence suit can be raised against a physician or......

Words: 892 - Pages: 4

Deathcapmushrooms

...transcription phase), thus giving it a base from which to build a template for the copy that'll follow. This way, a single gene can be copied into hundred, thousands...millions...eh, you get the idea. Works sort of like PK-Unzip, just WAY more efficient (and to think that nature came up with the idea first...). – So? ● Wanna take a stab at what the amatoxin does? – DING DING – DING! THAT'S RIGHT! IT'S FIBRINOLYTIC AND STOPS BLOOD FROM CLOTING! No...wait...that doesn't sound right... Sorry. Just having fun... ● As I was saying... – The amatoxin found in the deathcap mushroom actually blocks the action of the mRNA polymerase. ● ● ● No transcription. No translation. Cellular breakdown, cellular death and eventual organ system failure and death of the organism. Since there is no longer any essential cellular protein synthesis (back to the blocking of the mRNA polymerase), cellular function breaks down the cells die, but why the liver and kidneys? Basically, they are the bodies garbage dumps. Ewww... ● Mother mother used to make me eat them... – All the time...yet, most of the toxins are moved through the liver and kidneys, and the toxin of the deathcap mushrooms have a special affinity for the liver, so they tend to “clump” in hepatic cells and do the most damage there. Initial treatment is supportive – gastric lavage, activated charcoal to remove any remaining toxin in the GI tract; hydration to correct electrolyte......

Words: 679 - Pages: 3

Lesson Outline for Sunday School

...law. Could I tell you just a quick story out of my own experience in life? Sixty-odd years ago I was on a farm in Canada. I had purchased the farm from another who had been somewhat careless in keeping it up. I went out one morning and found a currant bush that was at least six feet high. I knew that it was going all to wood. There was no sign of blossom or of fruit. I had had some experience in pruning trees before we left Salt Lake to go to Canada, as my father had a fruit farm. So I got my pruning shears and went to work on that currant bush, and I clipped it and cut it and cut it down until there was nothing left but a little clump of stumps. And as I looked at them, I yielded to an impulse, which I often have, to talk with inanimate things and have them talk to me. It’s a ridiculous habit. It’s one I can’t overcome. As I looked at this little clump of stumps, there seemed to be a tear on each one, and I said, “What’s the matter, currant bush? What are you crying about?” And I thought I heard that currant bush speak. It seemed to say, “How could you do this to me? I was making such wonderful growth. I was almost as large as the fruit tree and the shade tree, and now you have cut me down. And all in the garden will look upon me with contempt and pity. How could you do it? I thought you were the gardener here.” I thought I heard that from the currant bush. I thought it so much that I answered it. I said, “Look, little currant bush, I am the gardener here, and I know what I......

Words: 1626 - Pages: 7

Sort

...and Computer Simulation Clump Sort: A Stable Alternative To Heap Sort For Sorting Medical Data Visvasuresh Victor Govindaswamy Matthew Caudill Jeff Wilson Computer Science Texas A&M University-Texarkana Texarkana, USA lovebat814@yahoo.com Computer Science Texas A&M University-Texarkana Texarkana, USA Computer Science Texas A&M University-Texarkana Texarkana, USA Daniel Brower G. Balasekaran, FACSM Computer Science Texas A&M University-Texarkana Texarkana, USA Medical and Sports Science Nanyang Technology University Singapore Abstract—Sorting data sets are a thoroughly researched field. Several sorting algorithms have been introduced and these include Bubble, Insertion, Selection, Shell, Quick, Merge and Heap. In this paper, we present a novel sorting algorithm, named Clump Sort, to take advantage of ordered segments already present in medical data sets. It succeeds in sorting the medical data considerably better than all the sorts except when using totally non-clumped data. In this test using totally nonclumped data, Heap sort does only slightly better than Clump sort. However, Clump sort has the advantage of being a stable sort as the original order of equal elements is preserved whereas in Heap sort, it is not since it does not guarantee that equal elements will appear in their original order after sorting. As such, Clump Sort will have considerably better data cache performance with both clumped and non-clumped data, outperforming Heap Sort on a modern desktop......

Words: 1753 - Pages: 8

Sort Ofs

...plants and animals. For example, as temperatures get warmer, many plants are starting to grow and bloom earlier in the spring and survive longer into the fall. Some animals are waking from hibernation sooner or migrating at different times, too. * Forests Forests provide homes for many kinds of plants and animals. They also protect water quality, offer opportunities for recreation, and provide people with wood. Forests are sensitive to many effects of climate change, including shifting weather patterns, drought, wildfires, and the spread of pests like the mountain pine beetle. Unlike some animals, trees can't just get up and move when the temperature gets too hot or other conditions change! * Recreation In addition to causing all sorts of problems, such as heat waves, droughts, and coastline damage, warmer temperatures could also affect people's jobs, recreational activities, and hobbies. For example, in areas that usually experience cold winters, warmer temperatures could reduce opportunities for skiing, ice fishing, and other winter sports. Also, rising sea level could wash away beaches. * Coastal Areas Global climate change threatens coastlines and the buildings and cities located along them. Hundreds of millions of people around the world live in low–lying areas near the coast that could be flooded as the sea level rises. Rising sea level will also erode beaches and damage many coastal wetlands. Rising sea level and stronger storms caused by warmer oceans......

Words: 8168 - Pages: 33

Marketing Management - How Did Tesco Use the Information Collected to Modify Its Marketing Strategies What Sort of Benefits Was the Company Able to Derive as a Result of Such Modifications

...maintain the ‘freshness’ of the Absolute campaign? Discuss with respect to the brand’s association with different media: art, fashion, technology and music. 3. Even though Absolute ads have been depicted in different media, the central theme of the campaign has remained unchanged (the bottle and the two-word slogan) over the years. In light of the above statement, do you think that the campaign will manage to hold sway or lose in impact in the near future? Give reasons to support your arguments. 1. Analyze Tesco’s Club cards scheme in depth and comment on the various customer segmentation models the company developed after studying the data gathered. 2. How did Tesco use the information collected to modify its marketing strategies? What sort of benefits was the company able to derive as a result of such modifications? 3. What measures did Tesco adopt to support the CRM initiatives on the operational and strategic front? Is it enough for a company to implement loyalty card schemes (and CRM tools in general) in isolation? Why? 1. How has Preta Manger positioned its brand? 2. Explain how the different elements of the services marketing mix support and contribute to the positioning of Preta Manger. 1. Explain how you will methodically go about compiling the requested information covered in the seven questions for management. Include in your explanation an estimate of the expense involved in obtaining the information. 2. Develop a 10-question questionnaire......

Words: 827 - Pages: 4

Working on. Sort of

...Reading Strategies Worksheet Identify two reading goals, one short-term and one long-term. • Long-term reading goal: • Short-term reading goal: Write a 100- to 150-word response to each of the following questions: • How do you currently approach the weekly readings in the course? I would fix a schedule first and make a routine. Then stick on the plan and keep the tools ready for the reading like books, documents etc. When I do my weekly readings for this course I tend to first find a quiet place that is free from distractions. Then I read a chapter at a time, highlight the information I feel will be on a test or that I need to study, and then I take notes. After I have completed those steps, I like to review my notes. I also frequently read the chapters over again so I can refresh my memory on the subject. Taking these steps to learn the information will ensure that I am prepared for future tests. Also, reviewing my notes and chapters helps me retain the information much better. • How might you incorporate three of the suggestions covered this week into your study time? To incorporate three of the suggestions covered this week into your study time you have to prioritize. Make a list of all you do during the week, adding in these three things. Choose what you absolutely must do, and what you can do less of, like maybe watching TV. After I read this week’s chapter, I have learned several tips and strategies on how to read and study more......

Words: 355 - Pages: 2

Factors Affect the Academic Performance of Selected Working Student Chapter 1 the Problem and Its Background Introduction / Background of the Study Student Jobs Have Become a Sort of Trend Among Students Around the

...Factors Affect the Academic Performance of Selected Working Student Chapter 1 THE PROBLEM AND ITS BACKGROUND Introduction / Background of the Study Student jobs have become a sort of trend among students around the world, who want to work while they are studying. In short, the term that suits this trend is 'Earn and Learn' policy. Other reason why student jobs are popular among students is they help to cope up with the constant increase in tuition fees, and a way to afford further educations. The problem has been developed with the question as to how the corresponding workloads and required working hours of working students affect their academic performance at University of Caloocan- Camarin Campus. As a researcher, the main purpose of the study is to know the factors that affect the academic performance of working students. In addition, this paper aims to provide encouragement and motivation to all students especially those who are financially distressed to pursue and finish a college degree in order to be competitive in the future and be able to realize their goals and aspirations. It may also provide learning experiences and information to other students who are not working. In order to accomplish our objectives, we adopted several methodologies in obtaining data and information such as conducting surveys by providing questionnaires to our subjects, getting information in the internet and conducting interviews personally and honestly with our target subjects to......

Words: 323 - Pages: 2

Projectile Otion in Sorts

...A projectile is a body in free fall that is subject only to the forces of gravity (9.81ms‾²) and air resistance (Webster). It was Galileo who first accurately described projectile motion. He showed that it could be understood by analyzing the horizontal and vertical components separately. No one had done this prior to Galileo. People use to think that when something is shot in the air it goes in the air and some how hit something and explode, before Galileo which followed largely Aristotelian lines but incorporating a later theory of "impetus," which maintained that an object shot from a cannon, for example, followed a straight line until it "lost its impetus," at which point it fell abruptly to the ground. Later, simply by more careful observation, it was realized that projectiles actually follow a curved path. Yet no one knew what that path was, until Galileo. There was yet another brilliant insight that led Galileo to his most astounding conclusion about projectile motion. First of all, he reasoned that a projectile is not only influenced by one motion, but by two. The motion that acts vertically is the force of gravity, and this pulls an object towards the earth at 9.8 meters per second. But while gravity is pulling the object down, the projectile is also moving forward, horizontally at the same time. And this horizontal motion is uniform and constant according to Galileo's principle of inertia. He was indeed able to show that a projectile is controlled by two......

Words: 1378 - Pages: 6