JosAH 11,448
Recognized Expert MVP
Welcome back to the Sorting article.
For completeness, so you can copy and paste this sorting utility straight
in your own private back of tricks, here is the entire class: -
public final class HeapSort {
-
-
private HeapSort() { } // no istances of this class possible
-
-
// given a Sortable, build a heap starting at node i. There a n nodes in total
-
private static void heapify(Sortable s, int p, int n) {
-
-
for (int r, l= (p<<1)+1; l < n; p= l, l= (p<<1)+1) {
-
-
// l is the maximum of l and r, the two subnodes of p
-
if ((r= l+1) < n && s.compare(l, r) < 0) l= r;
-
-
// check if parent p is less than maximum l
-
if (s.compare(p, l) < 0) s.swap(p, l);
-
else break;
-
}
-
-
// build a heap out of the Sortable in place
-
private static void phase1(Sortable s) {
-
-
// heapify all the non-leaf nodes
-
for (int n= s.length(), p= n/2; p >= 0; p--)
-
heapify(s, p, n);
-
}
-
-
// sort the Sortable
-
private static void phase2(Sortable s) {
-
-
for (int n= s.length(); --n > 0; ) {
-
s.swap(0, n); // put the root element in its place
-
heapify(s, 0, n); // and restore the heap again
-
}
-
}
-
-
// driver for the worked methods
-
public static Sortable sort(Sortable s) {
-
-
phase1(s); // build initial heap
-
phase2(s); // sort the sortable given the heap
-
-
return s; // return the Sortable for convenience
-
}
-
}
-
This class takes about one page of text in my VI text editor. Let's step back
a bit from this code and realize what we've just created: this sort algoritm is
very efficient and stable w.r.t. it's runtime. This implementation doesn't know
anything about what exactly needs to be sorted, i.e. it only uses the Sortable
interface.
The class is final and contains a private default constructor so there is no
way for anyone else to create an instance of a HeapSort object; because no such
object is needed: this class is a utility class with just functionality.
The first article explained a bit about the heap sort algorithm itself.
Now let's get back to our original problem: given the following two arrays: -
String[] first= { "Fred", "Barney", "Wilma", "Betty", "Bambam", "Pebbles" };
-
String[] last= { "Flintstone", "Rubble", "FlintStone", "Rubble", "Rubble", "Flintstone" };
-
We have to create a Sortable that can return the number of first/last names, it
can compare two first names (for example) and it can swap two elements in both
the first and last name arrays. We need to sort these two array according to
the first name; the other array just needs to 'follow' i.e it last names must
correspond to the first names after the sort has finished.
Here's the complete example without many comments: -
public class Flintstones implements Sortable {
-
-
private String[] first;
-
private String[] last;
-
-
public FlintStones(String[] first, String[] last) {
-
-
this.first= first;
-
this.last = last;
-
}
-
-
public int length() { // interface implementation
-
-
return first.length;
-
}
-
-
public int compare(int i, int j) { // interface implementation
-
-
return first[i].compareTo(first[j]);
-
}
-
-
private void swap (String[] s, int i, int j) { // private helper method
-
-
String t= s[i]; s[i]= s[j]; s[j]= t;
-
-
}
-
public void swap(int i, int j) { // interface implementation
-
-
swap(first, i, j);
-
swap(last, i, j);
-
}
-
-
public static void main(String[] args) {
-
-
String[] first= { "Fred", "Barney", "Wilma", "Betty", "Bambam", "Pebbles" };
-
String[] last= { "Flintstone", "Rubble", "FlintStone", "Rubble", "Rubble", "Flintstone" };
-
-
HeapSort.sort(new ArraySortable(first, last));
-
-
for (int i= 0; i < first.length; i++)
-
System.out.println(first[i]+" "+last[i]);
-
}
-
}
-
So what was this 'Tip Of The Week' all about? It showed that you can sort not
just arrays or Lists, but anything that implements the Sortable interface. It
also showed some of the gory details of the heap sort algorithm.
If I don't get kicked out now I'd like to tell something about permutations
and combinations in a next Tip Of The Week and how they can be efficiently
generated without much hassle.
kind regards,
Jos
0 5432 Sign in to post your reply or Sign up for a free account.
Similar topics |
by: darth |
last post by:
Does anyone have heap sorting with queue(doublely linked list) in C?
I have heap sort with array but with queue, it's somewhat hard.
|
by: Bonj |
last post by:
hello
this is a purely algorithmical question but if i have posted to an
irrelevant group, apologies.
can anyone point me at some good tutorials or info about the steps involved
in creating a high-end generic binary tree (or, ternary search tree).
The basic method I've got at the moment is having a resource file containing
a series of data structures (which represent strings), specifically
organised such that a test string can be matched...
|
by: songie D |
last post by:
I am looking to write a very fast algorithm to merge ranges.
e.g. if it was input the following ranges (1,3), (4,6), (9, 12)
it should return exactly the same thing.
However if it's passed (1, 5), (3, 8), (10, 12) then it should return (1, 8), (10, 12).
for this i'm looking to load a big array onto the heap, use memset to
set the ranges, then read it back.
Technically, I would only need 1 bit for each valid number in the range (the...
|
by: codergem |
last post by:
The following code is for heap sort but its not working properly.
According to my analysis the Logic is correct but still its not showing
the correct output.
Thanks.
#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
|
by: Raj |
last post by:
We are on a db2 v8.2 (fix 8) with DPF & intra parllelism. Below are
sort related configuration settings
-----------------------------------------------------------------------------------------------------------------------------------
Sort heap threshold (4KB) (SHEAPTHRES) = 200000
Sort heap thres for shared sorts (4KB) (SHEAPTHRES_SHR) = (SHEAPTHRES)
...
| |
by: Nick Valeontis |
last post by:
I know how to use Icomparable.
However, I can't figure out how to sort a generic linked list? (without
writing the algorithm)
Lets say I have something like this:
class DisJunctiveConstraintList : LinkedList<DisjunctiveConstraint>
|
by: Woody Ling |
last post by:
In 32 bits DB2 environment, is it meaningful to set sheapthres larger
than 256MB for the following case..
1. Intra-parallel is ON
2. Intra-parallel is OFF
|
by: JosAH |
last post by:
Greetings,
I was asked to write a Tip Of the Week; so here goes: a lot of topics are
started here in this forum (and a lot of other forums too) mentioning a
problem about sorting data.
Examples of two main problem scenarios are like this:
1) an array containing a first name and another array containing a last name
and possibly a third array containing the age of a person; how to sort the
|
by: Alan |
last post by:
I was wondering if anyone had design advice on this. . . . I am
doing some mathematical operations looking at different metrics for
data (in objects) I have captured. The object class has several data
attributes, say: metric1, metric2, . . . metricN. These are different
metrics on which I am running statistics.
There are a number of operations I have to do on these objects for
each metric separately: sort, group (i.e., group a list of...
|
by: sophia.agnes |
last post by:
Hi all,
Is there a simple algorithm to implement in heapsort???
this is the program i found in my college D.S notebook
#include<stdio.h>
#include<stdlib.h>
void heapsort (int, int);
|
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, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| |
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
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 protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
| |
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |